i used to play deity only, switched down to immortal or flexible difficulty after the free promotions patch.
economy is the most important part on this level, markets, courthouses and kilmorph temples have to be everywhere. after a certain amount of cities you should consider it very well if you want to keep new cities.
by the time t3 and t4 units emerge the game gets a lot more difficult if you did not manage to carve yourself a standing in the world. magic is a big advantage but you have to be very careful not to get crushed by sheer numbers and better units. it can happen that you walk a stack of 2 heroes and 30+ units near a city, call the maelstroms etc you have available and have an empty field when its your turn again.
you have to field a big army - the main work will be done by few highly promoted units, but you need a lot to cover them, take over newly captured cities and defend against counterattacks.
one, sometimes two enemies at once can be fought. you have to be very careful about diplomacy - which is quite hard if everybody comes knocking to ask you to join their war (how i hate this...). vanilla/bts is a lot easier to play diplomacy-wise.
play aggressive - you can still make peace if you encounter a force too big to wield. on the other hand it is a lot more difficult to stop a declaring AI to war against you.
in the late game i try to have a strong high mobility troop i can dispatch to handle emergencies. 2-3 mages and 8-10 chariots.
guild of the nine also works wonders, one of the most important wonders ever as you can buy defenders in new cities and strengthen your front in backwards places when you get surprised. have hawks on all edges and check the AI diplo status to avoid these surprises.
in the very beginning the AI rexes like mad, a strong warrior force can take out a good part of any empire. watch out for doviello or varn gosam, they tend to rush the human player and will roll over you if you have your elite troops warring on another front.
in the beginning it is the ability to farm XP on barbarians and choose promotions wisely that helps in warfare (early heroes like saverous help, too), later on it is economic superiority (having a bigger empire, higher GNP etc) and the use of magic that levels the advantages of the AI.
if you want to train for survival play the survival challenge (OOC, deity, raging barbs, always war, 3 allied AIs, at least one barbarian, one-piece-map). if you manage to win it on small pangäa you are on the right way
