In order of my preference:
Master of Orion 2 - arguably the best space strategy game (similar to Civilization in terms of scope)
Master of Orion 3 (with a major mod overhaul using the mod "Strawberry") - more of a macromanagement strategy game concerned with government policies overall.
Total War (as noted previously) - I prefer Rome: Total War
Galactic Civilizations 2 - Nice game, but the combat is run like a movie; not much, if any tactics involved. The strategy aspect is very compelling though.
Ooh, just thought of a really old one I used to play a lot. If you don't mind using DosBox, this game could be fun:
Master of Magic - Civilization with competing wizard empires and fantasy units (including heroes that can become insanely powerful)
I know I downloaded this for free a few months ago... I'll find where I got it...
http://www.abandonia.com/en/games/189/Master+of+Magic.html