Galactic Civilizations has pretty decent AI. What's more, at higher levels it actually performs more intelligently (rather than just getting bigger bonuses). Add different behaviour for each civilization on the good-evil plane and you get great replayability.

Pity the graphics are crap though.