I applied after 64 days. That allowed me to make sure I didn't count wrong. Also, I didn't want to make the request on a weekend, and I wanted to wait for some pending charges to post.
I didn't want to wait much longer than 64 days because the only way my score could go in the short term was down. When I applied for AMEX, my balances and utilization were about as low as they could get. My score immediately dropped three points due to the AMEX pull. My next soft pull would have reflected the four points I lost due to the addition of the AMEX card. I wanted to get my request in before that pull.
I started at $15,000, requested $22,000, and AMEX countered with $21,200. That's probably not as silly as it looks because the $6,200 increase put my total limits at an even $60,000. The $60,000 comfort level may have been based on my income, which is more moderate than the OP's. But I'm betting that it was mostly based on the fact that five of my eight cards were opened during the previous seven months.
In the OP's case, I think I'd request $24,000 to hopefully avoid a proof of income request. Or go for $23,000 to double the starting limit.
