Since we're doing alternatives for Civ-lovers, I really, really enjoyed Galactic Civilizations II. It had the right mix of massive scale, diverse strategy, politics, and an interesting combat mechanic with user-designed units. Endgame is sometimes a bit weak, when it's obvious you've won and have to grind through a multi-hour campaign of genocide, but it's the only game that's come close to that feeling of depth and complexity I got as a teenager from the Civ series.