I'm not sure the OP would enjoy Planescape : Torment. He seems to look for a nice turn-based combat system, and combat is clearly not the strength of PST. I really enjoy this game (thanks GOG btw) but the very few combats I go through are not particularly enjoyable, and the class system is pretty weird. The game world and dialogues are amazing though, but it's almost more of an adventure game than a pure combat-oriented RPG.

Thanks for the link, this game looks awesome!

Oh that's right, it isn't turn-based. Well then I guess Fallout is my recommendation then.

So, how do you like Baldur's Gate 2?

The Realms of Arkania series is turn-based for the combat. All the various missions and locations should keep you busy for a few months.

I just remembered that Betrayal at Krondor is supposed to have a good story. I think it may be turn-based. I haven't played it though.

oh yes, yes, this

I recommend the Realms of Arkania games. They are available at this site:
http://www.gog.com/en/gamecard/realms_of_arkania_1_2
http://www.gog.com/en/gamecard/realms_of_arkania_3

They have turn-based combat, are deep, immersive, atmospheric and have good stories.
They not based on D&D but on a different pen and paper role playing system called "Das Schwarze Auge"
One interesting thing about this is that you not only roll and distribute points to seven positive attributes (wisdom, courage, charisma, dexterity, agility, strenght and intuition.) but also to seven negative attributes (superstition, acrophobia, claustrophobia, avarice, necrophobia, curiosity and violent temper.)

If you are planning only to play one game in the series, the second one "Realms of Arkania: Star Trail" is generally considered the best.

Really, Fallout 1 is a must. I'd say check that out first and then play 2 if you like 1 a lot.

After that I'd say Arcanum or, if you want to give the infinity engine a try, Planescape: Torment.

Hallo again!
Just bought Fallout 1 and wishlisted most everything recommended here - I think, after Fallout, Temple of Elemental Evil and then maybe Baldur's Gate are up next.
Thanks tons, guys!

Planescape Torment is a great RPG. The combat isn't difficult and in real-time, but the story is AMAZING. You should not miss this one.

A good choice! Fallout and Baldur's Gate are very good for choices and consequences and Temple of Elemental Evil and Fallout are very good for fun turn-based combat.