I think Civ4 (or indeed earlier Civs) is a very good standard for a challenging AI that M2TW should aspire too. However, I am not convinced that the AI is that much better than in TW games and suspect it may just have more cheats.

Certainly, Civ4 AI is no great shakes at war fighting - which is what we are demanding from the TW AI. I can squash waves of AI troops with virtually no losses because it does not fight smart. And this is with a much simpler "battle map" (moves are confined to a few squares, so presumably there are fewer options to evaluate). It's been a while, so I can't remember all the gory details but I do recall the AI lamentably fails to bring enough siege equipment to bring down cities (although the BI AI also has the same failing). On the few occasions I have invaded AI Civs, it has been like slicing a sausage - the AI has no concept of concentration of force and just happily sits with 3-4 stacks in each city, while I dismember it's empire of 12+ cities with a stack of about 8 units. I would say STW or MTW provide a greater threat for any given ratio of AI to player resources. I just booted up STW as Useugi - try defending Shinano in turn 7 against 2 invading armies; when you are outnumbered 3:1 on the battlefield, however smart you are, you're probably going down.

I suspect Civ is so challenging partly because it cheats so much. It pumps up its cities and its armies so you have to work like crazy to keep a lead. Even on noble (supposedly "fair"), I think it gets great discounts for upgrading its units, so you it's less likely you will see AI "peasants" fighting your knights. I have not looked under the hood, but the reason the AI is so strong at Monarch and above is not because it is any smarter at those levels, just because it gets some massive advantages.

However, I will say that I love the Civ diplomatic AI - the way AI factions have distinct personalities and the way many launch opportunistic wars, get weary, back off and later come gunning for a round two. I am a builder in civ - war fighting is too tedious in that engine - but it is thrilling to try to hold off aggressive Civs while I prioritise bread over guns. TW AI diplomacy is rather brain dead by contrast - they often start pointless wars, refuse sensible offers of peace, make ludicrous demands and do not simulate any recognisably human personality at all.