Imperialism 2 had pretty good AI on hard. Yes, you could fool it by oscillating armies between provinces but it was very ruthless at exploiting your weakness and coped admirably with the formiddable multiple constraints on your nation's development.

I also liked the threat of Civ2's AI on King and Deity - when the Mongols or some other aggressive/expansionist faction first appeared, you worried. Civ3 bored me, but I confess it may have been even harder than Civ2.

To be honest, although people complain, I think the battlefield AI does well in STW and MTW. In MTW, the weaknesses were more at the strategic level (build choices, failure to exploit sea trade). STW was pretty competitive.

Heroes of Might and Magic III had a non-too-shabby AI, both strategic and tactical. I disliked a lot of the game mechanics, but the computer could put up a good fight.

I've been less impressed with the AI of computer wargames, but have a soft spot for Steel Panthers. There is something about being remorsely pounded with heavy artillery on defence or blundering into concealed ambushes that gave a feeling of danger even if in reality you were going to win.