I'd say Civilization IV seemed to have the best AI I've seen, with the expansions, it can actually put up a decent fight without extra resources.  It still can't really exploit any weak spots you leave, and has problems with keeping more units than necessary on defense (many of them unupgraded from their original type), but at least it could produce a competitive empire without needing a massive handicap.

Battlefield Vietnam- an old(er, circa 2004) FPS game. Why? Well, the AI actually LEARNS from you, the player. As you get better, so does it.

CIV IV AI can be quite ruthless now ( I play on monarch so the AI get some bonuses as well).

Rise of Nations probably has the best I know, but it's not stellar or anything.

I uses the strengths of each nation to it's advantage. So for instance, if it's russian and it has strong territory and attrition bonuses, it will build wonders that enhance that to really put the pressure on your empire. 

It uses defenses for what you'r attackign with. So if you have a lot of ground forces, it uses towers and fortresses. If you use sky it counters with AA guns.

I've also seen it attack with small armies on one side of your empire to draw your troops, then attack from another angle with a stronger force.

There are plenty of other examples, but really it's not comparable to a human, but still better than any other RTS's i've played.

I've heard good things about AI Wars.  But the best strat game AI...hmm...any mildly good chess program on its highest settings...that India Trading Company game isn't half bad in trading anwyay, player will kill the AI in war though.  SOMETIMES the AI in Empire: Total War (The RTS AI) seems to do well (On hardest).  The FIRST Gangsters game was pretty good from what I remember.

For strategic (empire-level) AI: 

Galactic Civilizations 2 wins that prize hands-down, especially with both expansion packs.  The computer-controlled races are pretty damned good -- sometimes, almost frighteningly so -- at reacting to the other races' plans and exploiting weaknesses (including my own). 

Honorable mentions: Sword of the Stars (Complete Edition) and Gary Grigsby's War Between the States.

For tactical (combat) AI: 

Shogun Total War retains the top spot in my personal list of games.  I've generally found it to be a competent opponent, and has in fact wiped the floor with me on any number of occasions.  The AI's only real weakness (at least that I've noticed) is that it tends to be a bit reckless with its generals.  Otherwise, however, it's awfully damned good. 

Honorable mentions: Medieval Total War (the original) and Sins of a Solar Empire. 

Sadly, I must agree.  Even in my beloved Shogun and Medieval, the strategic AI has always been somewhat weak, and this problem was only exacerbated in later games with the introduction of the 3D campaign map. 

Also, as you've already pointed out, diplomacy throughout virtually the entire series has been broken.  It wasn't *quite* so bad in Shogun (as it was, in fact, rather common during the Sengoku Jidai period for the various clans to betray each other at some point), but diplomacy been vritually meaningless in every other TW title since then -- and it should be a major factor. 

Do you mean the tactical battles or the strategic stuff?  They're both horrible but in different ways; even on VH/VH you could defeat fullstack armies losing 9 guys if you knew what you were doing, because the AI never adapted to what you did (and the combat mechanics were broken, which didn't help).  Every battle, same tactics, same result.  The strategic stuff on the open map was pretty poor (you built a fortress where? you refused what offer?) but really comes back to CA trying to invent difficulty out of nowhere.

I have to agree I didn't find it as galling in Shogun, but a combination of rose-tinted glasses and the simpler nature (7 factions vs more than a dozen, much simpler map, formalised diplomacy) probably figures into it.  It seems likely that as the games got more complex and the AI couldn't keep up, they kept up the pressure on player with things like 'spawn armies from nowhere' and 'attack the player even if such is suicidal' and the like.

Pnakotus, have you played Empire??  Anyway, I meant the tactical AI.  I've also had a much better time diplomatically...although there's some big problems they're hoping to fix in next patch for Campaign AI.  Anyway..

Bah, the quote button doesn't work.    No, I haven't played Empire (I got tired of buying broken CA games some time ago) but I have heard that the diplomacy is much improved.  From what I hear it's still sub-GalCiv2, but it's a step in the right direction.

Populous: The Beginning. Anybody else remember this game?

Course....it might be that a lot of the maps were 3v1 from the start.

OFP and Arma 2!

When it works, it really puts the fear into you. Unfortunatly it dosn't always work perfectly but what do you expect from a super hard core developer with a niche product? Certainly not CoD style scriptlols.

(Not OFP2:Console Rising though, which is an acceseable CM cash in built around the concept of OFP)

Where the hell did you hear that nonsense??  Whoever told you that was either lying, or utterly deluded.  The diplomacy in ETW is more broken than ever, especially since the last couple patches (1.2 and 1.3). It's gotten so bad, that players are now calling it the "Black Knight" AI (after the infamously hilarious scene from the film Monty Python and the Holy Grail).

Factions declare war on you for no reason, and -- more often than not -- from a position of weakness.  Also, it's pointless forming alliances with any faction that has territory bordering your own, as they inevitably break the alliance and declare war on you (regardless of whatever favors you may have done for them).  In addition, factions all too often reject even the most reasonable/generous of treaty offers....including and especially if they're on the losing end of a war with you, and their very survival likely depends on negotiating some sort of peace with your faction. 

Supposedly the 1.4 update coming out at the end of this month is going to rectify at least some of the problems with the rubbish diplomatic system, but I'm not holding my breath.