Good call on mass air. I haven't played deity (except a duel with Greece to get the achievement) but I could see how air would be a huge advantage, because the AI never has an answer for it.
Some random comments/observations, to clarify my points:
1. War to clear your continent is huge and allows you to have no standing defense, saving on costs.
2. More cities = more science. Expand as large as happiness allows. Trade routes should boost your economy and allow you to buy Colosseums for happiness.
3. You won't keep up on population. To keep tech parity (or keep it close), libraries are critical for their bonus and science specialists. Great scientists will eventually prove to be your advantage, perhaps allowing a mild slingshot to a more advanced military tech to stem the tide.
4. Be tactical. Do you go right for the AI superpower or try to pick off a smaller civ for their cities to establish a beachhead (and improve science)? When do you send over your heavily upgraded units from your first wars to attack (answer: immediately if you think you can take a city with them with minimal losses, wait until a critical military upgrade otherwise)?
All this said, there's not much you can do if a Greece or something runs over a continent quicker than you and establishes a large tech lead (and it's possible, especially if you fight an early war or attrition). But the AI is horrible at closing and overseas wars, so there's still a good chance you could win by diplo or space.
Oh, and prioritized wonders: Chichen Itza, Taj Mahal, Forbidden Palace. The Louvre is also high up there. I try to stay in a perpetual golden age from the time I take my continent through my first war or two on the next continent - it helps for cash rushing units to the frontlines, buying off city states, buying happiness infrastructure...