Europa Universalis II (a.k.a. For the Glory)
Steam is offering this, as well as Paradox's similar historical grand strategy games at 75% off, but the offer ends in 10 hours. It's a freaking awesome 4X strategy title, you can play as any nation from 1419 to 1819, England, France, Teutonic Order, Saxony, Iroquais, Cherokee, Aztec, Prussia, Ottoman, China, etc etc etc. The best part is the diplomacy; to declare war on another country you must have a casus belli, Latin for "cause for war", otherwise you take a -2 hit to your nation's stability, meaning you raise less taxes and have more risk of a revolt in your home provinces. You take a -1 hit for declaring war on a country with the same religion as you. You can get a casus belli by various means, if someone attacks one of your allies or vassals or someone whose independence you have guaranteed. Relations between nations go from -200 (most hated enemies) to +200 (best of friends) and can be modified by paying tributes, entering royal marriages, alliances and so on. It's a real-time strategy, but you can issue orders while paused, so it feels turn-based.
Space Empires series (number 4 is the best IMO)
Another excellent 4X strategy. This one is turn-based. The tech tree is absolutely massive. You start off only being able to colonise planets of the same type as your home planet (types are rock, ice and gas), but can research the ability to colonise others. Your biggest colonies will be on planets with the same kind of atmosphere as your home, as these do not need atmospheric domes. There's lots to do diplomatically, and you design your own starships and space stations by selecting a chassis and which modules you want to have on it, there are hundreds, maybe thousands of different modules to choose from if you research the entire tree. The galaxy is randomly generated and pretty huge. Star systems are joined together with warp points (wormholes). The massive array of different techs means a pretty limitless choice as far as what combination of strategy you adopt.
Both games have fairly steep learning curves, you will probably fail miserably the first time you play, as I did. I could say the same of Civ III or Total War though, which I also loved.