Whoa, were we playing the same version of GalCiv2? It does cheat at higher skill levels--it would be stupid to NOT make cheating levels after all, if you're good enough you want a lopsided game--and when I put it at the highest non-cheating level, I still trounce it and it still does stupid things like only research laser defenses when all I use is missiles. Sure, you might say, the other AIs have to worry about each other, but that's not true when I'm doing way better then the rest of them put together. I'm sorry. GalCiv2 might be a tiny hair above the competition...but I'm not convinced. Its AI is not revolutionary at all, and the game itself gets on my nerves (worst tech descriptions ever).
As for Civ4... Uh, I really hate to say it, but those complaints about how hard it is to build stuff, and how abusive the AI is at making cities? It sounds like you're just a scrub. :x Good players are REALLY good at optimizing workers and settlers. Really really good. Notice how the AI has more farms than you? Yeah. They're probably also making way better use of their gold, and buying things at the correct times (er...wait, sorry, that's every game BUT civ 4 in most of its gov types). I only say that because, having played civ type games for the last um...17 years?, newbies tend to think I'm cheating. >_>
Personally though. I don't really like being outsmarted by a computer. I've programmed AI, I know it's not a matter of being "smart", it's a matter of being programmed well...and I don't like battles of wits against some programmer. I just think of player-vs-computer TBS games as equivalent to Doom or something. The enemy has numbers. You have smarts. It's fun to outsmart your enemy, and beat the hell out of their superior stuff. If you want a smart enemy, play against a HUMAN. There is no substitute and never will be, at least not until AI is sentient...and then it won't want to play these boring games.
My favorite Civ-alike is Alpha Centauri, by a HUUUUGE margin. I rate the others about equal. (Except civ 3 below the others. Why do 3rd games always suck? SimCity 3 sucked, too.)