Most of the "good" TBS games for the PC have already been mentioned. You might try to get your hands on a copy Koei's "Romance of the Three Kingdoms XI". Mostly released for platform game sytems now, Koei did return to making a PC version after many years though mostly for the Asian market, but did release ...XI for North America as well in 2008 I believe (although difficult to find).

I remember playing Koei's older games for both the Nintendo (NES), Amiga and PC (DOS) recalling fond memories of those titles.

Romance of the Three Kingdoms

Nobunaga's Ambition

Bandit Kings of Ancient China

Genghis Khan

Chronology of turn-based strategy video games

I'd second Dominions 3.  Also, have you tried Paradox's titles?  Europa Universalis 3 and it's expansion packs can be had for cheap.  Also, they are releasing Hearts of Iron 3 this Friday.

For turn based, give Sword of the Stars a shot!

Ow, damn! I was going to get Dominions 3, but $55?!? Holy crap. I don't think I've payed that much for any game except Rock Band/Guitar Hero. $30 I'd blow for the hell of it on a game, but $55 takes it out of the range of a "something to toy with" purchase.

I think the price is largely due to the rather "epic" manual it ships with.  There doesnt appear to be a digital version...if so, Id imagine it to be cheaper.   There is a demo for it though.

In either event, its not really something you "toy around with".  It's far too dense and deep for that.  There have been better options listed in this thread for more casual fare.

Dwarf Fortress, in my opinion, is a contender for the best game ever made.  No graphics to speak of, but the gameplay is rich and deep.  It starts out like an oregon trail type game, then transitions into a sim-dungeon and ends as an empire management game.  It has a lot of micromanagement, but the ability to automate is second to none.  The learning curve is brutally steep and the interface is barbaric, but the game itself is well worth the price of admission.  It's free, so take a look if you haven't already.

I also just bought Elven Legacy which is sort of a modern Fantasy General style of game.  It's fun but it crashes on me occassionally.  Not a big deal since it's turn bsaed and autosaves, but still disappointing.

Dwarf Fortress, *sob*, the greatest game ever made ruined by a horrid inteface. If someone could wrap the game in a real interface, with mouse support, context menus, hover status (like hovering over a dwarf), I'd easily pay $100 for it. As it stands now, I mostly spent my time yelling at the computer as I slowly enabled/disabled the zillion jobs a dwarf could do every time I got a new influx of migrants or completely forgot which switch activated which floodgates...

I recommend the AgeofWonders:ShadowMagic  with the 1.4 patch  and also playing Dominions_3 with 3.23b patch.

I must be wierd. I don't play that many RTS/DOTA/RPGS. Somehow I made the cross over from FPS/ARCADE to RTS. Go figure. I'd recommend Metal Arms: Glitch in the System. Game is funny as hell at points. Creative guns. Very fast and a great game to vent on when another game out there (Sins, Demigod) is driving you knuts with glitches/bugs/exploits.

I know you hate RTS so I mention this game just to throw it out there. Anno 1404: Dawn of Discovery. Excellent game with great graphics. It is RTS but you can control the speed at which the game moves. I would describe the pace of the game as 'leisurely'. Things you probably won't like about it are: $50 right now on Impulse; it has TAGES, which is a downer for some people.

Civ4 is great; you can get it with all the new content, mods and both expansions for pretty cheap.  Colonization is a darn fun and interesting game now with the new patch (anybody know what I mean by "Kiss the Ring"?  Man, you will SO want to destroy the king by the end of that game).  And it's far from new, and may not run on your computer, but Imperialism II is a classic we played for years.  If they did a remake (nothing but graphics, and to make it work on most current computers) for Imp2, I would pay $50 for it without blinking.

That's a typical progression...  Anyone who starts at FPS/ARCADE eventually moves toward RPG or RTS and usually the final stage is TBS and RPG.

I'd love to if I could get my hands on an english copy of it for a reasonable price. But around here you only get the german version, or english versions for a price even higher that upon it's initial release...

In other words,

1. experimentation 

2. misuse

3. abuse

4. addiction and dependency

*Prognosis ------> Terminal* 

I've been playing King's Bounty: The Legend for several weeks.

While not a flawless experience, it is a fun tactical RPG (imagine HoMM meets Final Fantasy Tactics) with solid battle mechanics. It is available on Impulse, and a great value (I cannot precisely recall the number of hours that I have spent during my first run through the game, but I estimate that I am well beyond 40 at this point). It came recommended from some folks at Stardock, and I pass on that recommendation to fans of the genre.