Old and hard strategy games -
Populous 3: The Beginning (struggling to complete the game on my... 4th or 5th attempt right now.)
State of War (Virtually unknown, low budget RTS, same as with populous.)
Dungeon Keeper
Celtic Tales: Balor of the Evil Eye... or something like that (1994 DOS game, TBS, fun and addictive, but has a somewhat hard end, failed on my first playthrough, can play it on DosBox now.)
C&C Tiberian Sun (Old favourite, also best basebuilding of C&C series)
Some newer stuff:
Dwarf Fortress (Never really managed to get into the game because of the interface mostly, but following its development progress, hoping that it becomes more accessible to me within a lifetime)
Age of Empires III (Great fun in multiplayer with friends!)
Dawn of War (Even greater fun in multiplayer with friends, very fast-paced RTS, Dark Crusade is the best expansion to it.)
Borderlands (If you have 3 friends that you can regularly play together with, then this is good)