MOO2, Pax Imperia: Eminent Domain, and Imperium Galactica 2 were all excellent 4x games from approximately the same period. All three had excellent soundtracks, too.
MOO2 was the most primitive in terms of of its graphics and the turn-based system was a little archaic as well, but it is still challenging to play. The AI has no discernible weaknesses.
The other two, unfortunately, each have one "fatal" AI flaw that, once you discover it, pretty much makes it impossible for you to lose a game. However, both have excellent tech trees (the one for Pax Imperia may be the best I have ever seen, although it does suffer from the limitation that all races research the same items). Imperium Galactica 2 had nice ground combat options, but had the shortest shelf life of all, as it only runs on Windows 95 systems.
