Beat the AI to construction on every start on immortal or deity and say that again

.
There's a limit to what you can do if you don't get some insane commerce start. Cat/phant/axe will still have a window...but getting to it first and actually having enough production to mount a decent force? Doubtful you'll attain both without a nice start. The AI likes construction quite a bit (and it's not like it matters a great deal if they have construction, be thankful it didn't beeline monarchy then feudalism).