I'd say Battle For Wesnoth is very nice. I played it for a month or two, I mostly like them multiplayer though. I'm waiting for their new version to be complete, the 1.3.x is still in development but you can play the 1.2.x perfectly. It's nice if you download some add-ons for the game too.
Conquest of the New World, like Vperic said is very nice and challenging too. It's been a while since I've played it though.
About the Civilizations, I preferred Civ 2 the most, I liked the way everything worked. Civ III was nice, but I thought it was Civ II all over again with just better graphics. Civ IV is very nice, I like all the new features. It's quite easy on the easier difficulties while in Civ II I could hardly survive on Chieftain I think.
I do believe they're all very good, but they can take a long time. If you like that then there's an option in the fourth game to make games last longer
Age of Wonders seemed very good, but I never bought it, I just played the demo.
The Heroes of Might and Magic series were quite nice too and if you have some friends over for like a few hours every day you can have even more fun.
Castles II isn't really TB but I thought and still think it's a great game, I don't think it works on XP though.
Risk is a very good game and very hard too.
Master of Orion II (I didn't like the third) is a very nice Space TBS. It has very nice features and it's a game that's easy to learn and hard to master, somewhat like Battle for Wesnoth I believe. It had a similar tech-tree to Civ except it's in space
Btw, there's freeciv, which is an open-source version of Civ II out there. It's free, so if you want to try out some kind of Civ II (they changed some features, added others...) it's a good place to start to see if you'll like the Civ series.
The Total War series are worth trying too. Lords of the Realm II (I think there's a third out there too though) is nice, battles are a bit cumbersome, but it's a nice game. Lords of Magic too. Both are TBS, Lords of Magic is in a fantasy realm though. I couldn't get it to run on XP though.
Quite a long post and I think that's all I know about TBSs so...
Oh, Gangsters : Organized Crime, great, great game.... Unlike anything you've ever seen and really, really difficult, at least for me.