Stars!, MoO2, HMM 1-3. They are not amazing, but compared to them GalCiv2's AI is a retarded chimp with Down's syndrome that drank a gallon of fermented palm sap.
Hmmm. Two of those I'm not going to touch on - Stars! because I haven't played it enough to have an informed opinion on the AI; HoMM 3 for the opposite reason - it's one of my most-played games of all time, so while I find the GalCiv 2 AI lightyears more challenging than HoMM 3's AI, that's possibly just because I'm so familiar with HoMM 3's AI.
The rest, I'm gonna have to disagree with. HoMM 1's AI is... really not good. 2's AI is okay, but IMHO it has a few significant flaws that really keep it from being in the same league as GalCiv 2 - most notably its tendency to always target the highest HP stack. Actually, I think that's a good way of putting it. HoMM 2 has got decent strategic AI, but its tactical AI is abysmal.
MoO 2 is a tough one. I think the game has got deep AI and interesting AI. I think the game's AI is better than GalCiv 2's in the sense that it tends to have a lot more personality and is generally more fun to play against. However, I would say that it does not understand its own game as well as the GalCiv 2 AI does, and as a result does not play its game quite as well. Part of this is due to its Civ-like tendencies of assigning each faction specific personalities, which leads to certain factions simply being bad at playing the game, no matter what, because they're assigned a strategy that isn't very good (the Trilarians come to mind, poor bastards). GalCiv 2 AI does that to a lesser extent, but there's still usually some surprises (at least in my experience) as to which AI will make it to the end-game. In MoO 2, unless the player does something specific to curb them, the Psilons and the Sakkra will always,
always be the strongest AIs by endgame, while sides like the Trilarians and Mrrshans are again almost always going to be in a terrible position.
I guess in a way this makes MoO 2 "better" because it means that races like Sakkra and Psilons will always pose a challenge? But to me that's not a good sort of better.
In any case, even if it did have better AI, at most the difference is marginal. Certainly none of those games make GalCiv 2's AI look like a "retarded chimp with Down's syndrome that drank a gallon of fermented palm sap." Plus AFAIK the GalCiv 2 AI's cheating isn't nearly as outrageous as MoO 2's AI at higher levels, and to me that's another big factor there. Any AI can be challenging if you give it enough bonuses (well, maybe. Civ V and BE seem to be doing their damndest to disprove that hypothesis), but GalCiv 2's AI doesn't start the really bad cheating until Masochistic - the tenth difficulty level and the fifth above Normal. "Tough" is the difficulty setting where the AI play their best and don't cheat at all, and to me the AI there is significantly better than the AI on comparable settings in other games (Average in MoO 2 and Rook in HoMM 3).