Elven Legacy and Fantasy Wars are both very good games, then only problem is sometimes they feel more like puzzle games, because if you make just one single wrong movement you are basically f*cked. So yes, Elven Legacy is a pretty good game and is also insanely difficult, but King's Bounty: The Legend is way more enjoyable and rewarding.

Defiantly put in a vote for the Fallout series, that game has an excellent turned based combat system to it.

Jagged Alliance the best turn-based game I've ever played.

Eh, I never thought much of the combat system in Fallout 1 & 2, because of some of the tedious encounters with large amounts of non-combat NPCs, just a bunch of people just running around waving their arms. It also gets ridiculously redundant after a while.

I can recommend you both the Fallout and Jagged Alliance series.
Not many games give you so much value for your money.

I suggest maybe looking into the first Age of Wonders game. It had a half decent interface, plenty of units, good sized maps and interesting story.
Also, not to overlook the obvious but GOG has multiple versions of the ultimate turn based strategy game available: Chess.

I'm in shock that everyone forgot the Battle Isle series. :(
Being Battle Isle: Andosia War the last one of the series which is a very good Turn-Based Strategy game.
Check it out if you can still can find a copy at the discount bin or something.

Turn-based strategy definitely covers a lot of different types of games. For something similar to King's Bounty, I can reiterate that Age of Wonders is pretty great.
Two games that haven't been mentioned are Master of Magic, a global strategy game akin to Civilization, and Silent Storm, a turn-based squad combat game.
Incidentally, does anyone know where I can get ahold of Age of Wonders: Shadow Magic for a reasonable price (i.e. not this)?

oO $300 ? And $59 for a used version of AoW, that s insane. Sooner or later gog will release it, you better be patient :)

$308? Holy crap I have that game at home.

Who wouldv'e thought that some video games would ever be worth more than some lottery tickets.
$308 bucks, Yikes!
I just finished an E-Bay search....$65 US

Got a lot more than I expected. I actually made a list so I'll look into them all once I have the time.
Thanks.

Dominions 3 would probably also be a good one, or at last down the line once the feet get wet.

Fallout was definitely good stuff, but yes it can get a bit repetitive. Great overall feel though and the actual combats are fun. The repetitive stuff is more in the walking about.
HOMM2 was very good and very fun.
Galactic Civilizations is a really fun great game, but agreed with another poster that the combat is not so hot. It's everything around the combat that's great.
X-Com has the best turn-based tactical system I've seen yet and is one of the only games I've ever played that is anything like actually "scary." I jumped many times at the appearance of an alien, and was horrified many times at the appearance of an alien that makes people into zombies at breakneck speed. Nooooooooo. ........
Am playing Disciples 2 now. I've been playing it obsessively for the last month and a half, and there is a ridiculous amount of gameplay. I haven't even gotten through the first game yet, and part of the package includes a couple of expansions. Different characters play quite differently, and it's a lot of fun figuring out through experience which of a bunch of different hero leaders and fighting units you want to use and develop. This is also one of the few games that I've found is worth playing through a campaign in, as usually sandbox play allows for so much more creativity. Anyway, this is a very good game indeed and a tremendous value.

Short version: King's Bounty is better. But then King's Bounty is one of my favorite games, so that doesn't really say too much.
And while I could do a longer version it's easier just to refer you to the two demos: Fantasy Wars and Elven Legacy.