It's possible to win Immortal consistently. Not sure about Deity, I can't seem to get much beyond 50% odds. Still, that's a lot better than fair odds (which would imply winning 1 in 7 games on stanard settings).
As for how to win against high-level AIs... I don't think there's an ideal cookie cutter strategy. Deity is utter chaos for me (I don't win under my own power, I look for openings to let one AI win the game for me...) so the following assumes Emperor-Immortal:
I either build the majority of wonders or out-expand the AI by a comfortable margin - crashing one's economy in the process if fine as long as we get to recovery eventually (i.e. avoid getting stuck at 0 research before Currency/Code of Laws...).
My goal is around 12 cities at 1AD, more if I forgo wonders (apart from the Great Lighthouse which I always go for if the map warrants it).
The key is to strip away what you don't need. No unclaimed land and diplomacy is well in hand? You don't need military beyond a garrison warrior in each city.
Have a wonderspammer nearby? Amass an army since you can get cities and wonders for free.
Most players don't emphasise short-term rewards enough... something as basic as settling on a plains hill can make a city become an asset instead of a liability in short order.
War is a great tool to make the AIs throw away their production bonuses... possibly with one another (I love to scavenge cities from an ally who does all the work...), but being the victim isn't always bad.
Whether you're encouraging them to throw their units at an impregnable fortress or whether you pick theirs apart with siege and city raiders in a city without cultural defense... loss rates should be well in your favour. This softens the opponent up for an eventual push, and if they attacked you there won't be any diplomatic repercussions.
Many of these are probably pretty basic for an Emperor player... but getting into specifics fails to address the point that Civ4 is a surprisingly deep game where radically different approaches can be viable.
Very interesting analysis, thanks! I guess the main problem is how to balance military prod/wonders/expansion - and I have also realized CIV IV is deep, which is of course nice. 12 cities before 1 AD sounds very tough. Which leader do you usually play?
A couple of comments/questions:
1. I usuall feel one should found one religion, bc of shrine and happiness. And this religion is usually judaism if I have stone nearby. Also monotheism is good for organised religion civic. Otherwise I go for meditation (which I usually lose) and then try to build oracle and found confucianism.
Maybe playing a non-religous game but with more wonders?
2. To be able to expand and have many armies requires code of laws + feudalism (so one can get vasslage = many units). I dont see how this is possible before 1 AD. My main problem is that the prets become obsolete before these techs are achieved. This means I can only take cities a very bounded time with the prets and then economy breaks.
3. Is epic harder than normal speed?
4. Usually I let the first city grow to size 3 then build worker if there is gold or somethig interesting nearby; in other case i build settler.
Then comes the big question how one could cope without stonehenge and / or pyramids. So i usually try to build on of them. I like wonders that promote great enginneers since those can be used to build more wonders..
5. What is actually the benefit of settling a city on a plain hill? Shall one plan cities not to overlap in the strongest sense? Meaning there should for instance be no more than 3 tiles overlap. I am also doubtful of founding cities close to deserts. I hate deserts.
Best,
Alarik