I believe many HoF games (if not all) are played on maps that are selected for good starts.
I believe some of the players actually use(d) a program that randomly generates maps and then calculates the potential score a player can get on the map based on land area.
I know I read such in a forum post some time ago. I think Moonsinger may have written the program, but I can't recall.
If I were trying a Deity/Sid game and was not used to playing at those levels, I would look for a start on grasslands with hills close by, a river, and one or two cattle. Keep restarting until you get that.
Some people like island starts - so pick archeplago. I prefer not starting on an island, because if you are falling behind, attacking a civ close in size to yours can give a rapid boost to your civ, and building up a navy to transport troops is time consuming.
Its been some time, and I've never bothered with the War Academy myself, but as I recall, my pattern for high level games was usually the same:
1) build as many settler as you can as fast you can (settler factories)
2) keep one or two workers per city
3) micro manage - every time a city grows in size, expands its borders, or workers improve a plot, open up the city window and make sure the citizens are working where you want them to be - I try to emphasize growth over production, switching worked plots when the production will not interfere with growth and vice versa (most frequantly occurring when a city is building settlers and workers).
4) Concentrate on defensive units unless preparing for an invasion
5) At some point find a fairly close by civ that is roughly the same size as yours, and invade
6) Use artillery, lots and lots of artillery, for invasions edit: but not until cannons at the earliest
7) Use gold to buy improvements, waiting one turn so the cost drops
When it comes to war, I try to have alot of workers - a LOT of workers -available to build roads/railroads quickly, and I purchase temples, walls, and barracks in conquered cities asap. On huge maps, I have clumps of 24-34 workers stacked up waiting for war, maybe 2 or 3 such stacks, depending on how late in the game it is.
I also never let my offensive units travel without a few defensive units to soak up attacks. Most wars are wars of attrition, so DON'T LOSE TROOPS.
Now, granted, these ideas may not work for everyone, and I admit I'm a bit quirky with my playstyle, but it seems like all of my high level games fell into this pattern.
I think the only thing that can foul up this approach is a superpower coming after you early on, or getting boxed in. So being able to predict AI behavior is important.
Oh, I almost forgot - its been awhile - but tech trading gets important too at some point, maybe around Emperor. Have to be sly, and learn what the AI is going to go after, and what trades they are likely to make. Even on Regent this may matter.
As an example, I'm playing on Marla's world map as Germany, Regent, starting with 3 cities. Russia starts with... maybe 30 cities? I was at war with Russia, and had riflemen, and Russia sent an infranty unit at me. I was kinda surprised they were that far ahead of me in the tech race.
As it turned out, I restarted because I had made a few modding slip ups, the main one being I had forgotten to give all the artillery units lethal bombardment.
In the next game (on Regent), I completely avoided any of the unnecessary-to-advance era advancements (I'm a bit spoiled on Regent), and then bee-lined for replaceable parts, and was way ahead in the tech race. I was able to trade for the techs I had forsaken with much weaker civs also, so still was able to build the wonders I wanted, like Magellan's.
The lesson learned was that I played smarter regarding research, and it meant about an 8 or 9 tech difference when I got to the same point in the game - having done nothing else different.
And one sneaky tip I have is whenever you have a chance to trade a civ for one of their workers, do so, the earlier in the game the better. Use these to speed up settler production or add growth to one of your cities that is emphasizing military production.