Medieval 2 Total War - A mixture of turn based world map and massive real time battles. Far too much content for one game, then the expansion adds several more campaigns from across the world on top of that. For the price it can't be beaten.
Company of Heroes - Uses an improved version of the Dawn of War gameplay without the stripped feeling that Dawn of War 2 had. The campaign has many truly great moments.
Sins of a Solar Empire - Command entire systems, develop worlds and space armadas and conquer those of your enemies. I'm not normally into space games. But this one is certainly an exception.
Supreme Commander - Spiritual successor to one of the best RTS ever made. It shows.
World in Conflict - Fast paced RTS with no base building. Can be a tad too simplistic at times. But generally very enjoyable and very prettyful.
GOG games:
Commandos 2 - Exceptional WW2 tactical squad based game.
Earth 2150 & 2160 - Bags of innovation and brilliant execution. A tad slow, however.

- Another vote for Supreme Commander, and its sequel, Forged Alliance.
- Empire Earth and Empire Earth II
- Rise of Nations

What about Perimeter?

Perimeter will blow your mind. I wouldn't call it an "old fashioned" strategy game though.
Ah get it anyway. Stunning game.

If you really want an good old strategy game my recommendation must be 'Dune'.
Simple, easy to manage but not to master and very challenging.

Oh, and Battle Realms. That one's way underrated.
The Battle for Middle-earth 2 is surprisingly good for a licensed game. But personally, I'd recommend you try the Third Age mod for Medieval 2 instead. Bloody impressive!

This right here....
Sins is a kind of hybrid RTS/4x game.
Supreme Commander is an AMAZING game especially if you have dual monitors. But keep in mind it is more of a Strategy game and not a tactical one (Blizzard and Westwood RTS's should really be called RTT's).

If you are ever in the mood for some Turn-based strategy games you can always try out either King's Bounty or some of the Heroes of Might and Magic games...

I don't know if they're really all that tactical either, when you compare them to something like Commandos or X-Com.
To me they're action RTS games. Meaning they're about as strategic as an action RPG is an RPG.

I would actually say Battle for Middle-earth 1 was the better of those 2 games, they are both quite good fun though.
Starwars empire at war is another great licensed game if you install the Absolute Corruption Mod. It just makes the battles much bigger in scope and makes the space battles extra special. The ships are all to scale now, so tie fighters and bombers are tiny but you get a ton of them, the largest ships are HUGE. It makes for some really epic space battles in the game close to what you see in the movies with lazers everywhere. It does require a fairly beefy computer to play though with that many units. You can also install the unit cap mod if you want the battles to be even bigger.
[url=]http://empireatwar.filefront.com/file/Absolute_Corruption_mod;97499[/url]
http://empireatwar.filefront.com/file/Unit_Cap_Mod;80345

Thanks a lot! I've got Forces of Corruption, as it happens. One of my mega cheap eBay finds. But I haven't had much of a chance to play it yet. I'll definitely have to try these.