Each time I stepped up on the 3 stages - emperor, immortal, and deity, I needed to start being more and more agressive. Up until monarch, I could have won a game without having to war once. on these levels, u have to.
The simple reason is that the ai landgrabs way faster cause of its early bonuses, and because of later bonuses, his cities outproduce/outtech u.
U have to have around 1.5 times cities than the strongest ai to cancel out ai's bonuses. For example, i'm now on a deity game in which i have an equal number of cities as the strongest ai, all ai's way too friendly/vassals to each other, and i know that if i won't gain a few more cities i'm doomed.
I always choose early conquest - once with axeman/swordsman against one and once with maceman against another. no building wonders/religions/unnecessary bulildings, and make sure not to expand too fast prior to COL/currency. the axeman/swordsman gain me the $$ to be the first to alphabet even on deity.
I have seen early landgrabbing technics implemented by other players - initial settler goes as far as possible and colonizes right at the edge of the closest ai territory.
by the way, in which settings r u playing? if ur not on agg ai, i'd suggest trying agg ai emperor before immortal.