Out of the ones I've played, its tied between Europa Universalis 3 and EU: Rome. EU3's AI seems to be much more peaceful than that of Rome, but in general they're pretty good at making peace with you when it's in their benefit, then backstabbing you when you're unable to fight them without overextending your forces and/or driving your own economy to the ground. Though I haven't played GalCiv2 yet, which judging from the comments in this thread is a situation I should change ASAP

The first few times you play GalCiv2, you will be thoroughly convinced you're well on your way to dominating someone, only to have your sorry plans handed back to you. 

At least, I did.

As far as battle AI, Medieval Total War 1, Rome Total War, and Medieval Total War 2 all have decent AI. The diplomatic AI could always use some work. Empire Total War has been going through it's "ups and downs" as far as AI goes. At release the battle AI wasn't half bad. They had a patch later that completely ruined the battle AI for a while. It wouldn't stand and fire at enemy units, instead it would charge into mêlée head first. In a game that's mostly about shooting and having decent field position charging head long into mêlée doesn't fit with the over-all game plan. They fixed that with a recent patch though. I've enjoyed most of the Empire Campaigns I've played to date.

Right now I'd say one of the best 4X game AI's out is the Gal Civ 2 AI.

As I read people recommending Civ 4, I failed to see anyone mention the Better AI mod for it. The AI pumps out units like crazy!!

In case you just did not know about it, it can be found here: http://forums.civfanatics.com/showthread.php?t=297810

I think the best AI was in Kohan.  Part of it was the game mechanics.  All units, AI and player, had morale which would cause them to run to a friendly city when dying.  This solved the problem of the AI not caring for their units.  Any game that has units which level suffer when the AI throws them away.  Secondly, Kohan units were actually a small group with front line troops and rear support troops.  Since frontal assaults had to go though the front line units before it could reach the often deadly support troops, flanking was critical.  The AI would properly used fast mounted troops to attack the rear and flank once it had engaged the front line troops.  This would not only cut down the soft support troops but also made running away less likely to succeed.  Finally, the AI rarely attacked only one city.  More often you were attached on multiple fronts which can be a challenge in a RTS.  This is the only game where I've been able to find AI settings that gave me a 50/50 chance to win.  Great fun!   Also, co-op with your friends against the AI was not only possible but could be challenging.  If your friend was wiped out, you could give them some of your cities and armies to get them back in the game.  Overall a great experience.

Super Mario Kart for SNES hahahaha

Crysis has very good AI, but soemtimes it bugs and does something stupid. Just thought I would throw a bit of FPS in the mixer.

I know what the OP question actually asked for... but the best AI in any game is and will forever be SHODAN.

Alex kid

I'll throw in Hearts of Iron II and III (haven't played the original so can't tell) AI to the pile of good opponents. The third installment is especially engrossing because it has such a complex model of the command structure and warfare in general and plenty room to maneuver with a globe split into some 15 000 provinces. Compared to the way AI works in this game, both with diplomacy and more importantly, warfare, Total War series look like arcade slash-and-smash games.

I usually don't lose to AI in strategy games, but HoI AI can and does make me sweat at times. Just don't let it control *your* units because there it can do some stupid moves and then you'll sweat too, but for different reasons...

Romane of the 3 kingdoms XI has a decent AI, but the tutorial is like 4 hours long and you can customize and micro managment everything to the n-th degree.

Romane of the 3 kingdoms XI has a decent AI, but the tutorial is like 4 hours long and you can customize and micro managment everything to the n-th degree.

I think supreme commanders AI are quite impressive on normal. On easy they try to attack but often result in their commanders running around the base until they get destroyed. For people who dont know when a supreme commander blows up it goes in nucluear explosin. needless to say their base is almost always blow up

Hm funny...imho the TW battle AIs are horrible...at least it's very easy to exploit the AI's weaknesses. [It's quite easy to beat 3x++ bigger AI armies even.]