1. Freedom Fall

Bonus non-PC suggestions:

999 and Virtue's Last Reward.

If you have an xbox 360 or PS3: Tales of Vesperia

PC Titles
The Last Remnant
Diablo 1+Hellfire
Divine Divinity

Does it have to be on GOG?

Nope.

Hitman Bloodmoney
Chains of Satinav
Beneath a Steel Sky (This is already in your account - go play it)

1. Deadly Premonition (since you didn't specify PC only)
2. Bioshock Infinite
3. Ultima VII

-Avernum
-Geneforge
-Nethergate

Find extensive demos for all at spidweb.com . The worlds are carefully-designed and great fun to explore. The central plot in each is quite flexible-- You can choose a side or follow your own path. The graphics are dated, though I find them attractive enough (with the exception of the occasional color choice). The text descriptions of the places you visit and the people you meet are excellent. Avernum was the first I played of the three, and I found it totally absorbing.

I don't need any prize, thank you.

Damn you Licurg, you picked 2 of my choices.

Well, since someone already said Darklands, but the OP is looking for story driven games, I´ll say:

Heart of China
Superhero League of Hoboken
Sentinel Worlds I: Future Magic

I think the 3 of them are hidden gems.

I did it on purpose :D

Machinarium
Gemeni Rue
Beyond Good and Evil are also good choices.

To the Moon was already mentioned:

Gemini Rue is a great game, but Primordia is better. Beyond Good & Evil is exceptional, but far from being a hidden gem, I think...

So far, I'm enjoying this thread as much the OP should be. So many great games to discover! *o*

My opinion might very well be colored by nostalgia, but:

Spellforce is an RTS&RPG hybrid.

What sets this game apart from most others is the believable game world. And because this is an RTS, the believable game world is achieved through carefully crafted levels. Every map is full of elements that naturally expand the world. Ruins of ancient castles, caves filled with ghosts, forests with minotaur encampments, huge ominous dark towers and all of this is optional. There are even optional territories. There are at least two maps that you can skip entirely and you'll miss on some loot that's easily replaceable latter in the game, but why would you skip them. You feel like you need to explore more of this world and that's rare in a game.

Another thing that I liked about the game is that your character is a blank slate, in the sense that he has no previous memories. You might think that he's just another amnesiac protagonist, but what makes this protagonist better is that his past doesn't matter. His soul is suspended in a "rune stone" and he is summoned, when he is needed to fight. He doesn't mope around, he is given a mission and he sees it through, like every enjoyable character he is not an emo.

This is one of those games where finish the current mission and realize that its late, so you turn off the computer and as you lay in your bed, just before you fall asleep, you wonder how will the story finally end because it's been so gripping until now. And you can't wait to get back to the game, to play the next mission and experience more of the world.

Off the top of my head:
To the Moon
Driftmoon
Beyond Good & Evil

(also, thanks and +1 for the giveaway)

AlternativA

Trinity (the old Infocom text game)

I'll stick to just the two suggestions. If you've played the heck out of Torment and Arcanum and the other well-known classics, then nothing I can suggest will top your experience.

But if you want to try something you haven't played before and enjoy the story, the two listed above will fit the bill.

Cheers. I just got DS 1 expressly for this purpose. The game is installed and the mods downloaded. Will install and test the next time I have several unintereupted hours to throw at it (so, when my children move out of the house).