1. The Walking Dead (Telltale) - I almost cried and I don't even like adventure games!
2. Max Payne - The short noire story is well paced and well told.
3. Knights of the Old Republic - I like everything about it, really.

No GOG gems, I figured you've played them all :)

Thanks for your generosity and I hope you find what you're looking for! +1

Thanks for the giveaway, Aver! Here are my recommendations:

1. Black Mirror series - a trilogy of adventure games. Great, dark, gothic storytelling with fantastic atmosphere. Available on places like GamersGate and Amazon, but not GOG.

2. Realms of the Haunting - a supernatural action adventure unlike anything you've ever played before. Tons of cinematics and a truly epic story that spans multiple worlds. Probably the most underrated game on GOG in my opinion.

Game of Thrones RPG by Cyanide
- knowledge of the setting is recommended

Cave Story
Freedom Fighters
Grand Theft Auto III + Vice City + San Andreas
But really, Deus Ex is the best.

Prince of Persia The Sands of Times counts as already known big gem, right ? I actually told its story to a friend, once, as one would tell a fairy tale, and it was quite successful, even though I summarized it and couldn't convey the dialiogues, the actual evolution of relations, the narration, and the music. Still, it's the videogame I'm sometimes replaying as one would rewatch a movie, for the characters, the nice story and the way it's told. I completely disregard the sequels - Sands of Time has the right ending.

I may cheap with adventure games as they are very much based on narration, but I really love the Blackwell series, its characters, the dynamics between the investigator and the ghost, the general melancholy of the plots (ghosts always mean accomplished injustice, retrospection, and futile regrets). Wadget Games mean good stories, good writing, and quite moving (difficult) relationships.

And then Penumbra Black Plague, which is probably suggested already. A thriller very much based on dialogues and atmosphere, with devastating moments and very involving voice acting. I won't spoil much, but, well, it is good.

(I was also on the verge of suggesting Syberia - I didn't think much of it as I was playing, but for some reason the storry, settings, and characters have stuck with me, and I consider it as a little odyssey tale that does stay part in your universe long after you've finished the game. Actually, growingly so.)

Something a bit more obscure, you say.

Defense Grid: The Awakening. It's got a pretty decent story and dialogue going for it. Extremely odd, considering it's a tower defense.

Blackwell Bundle. Technically four games, but they're episodic and have an overarching storyline, so it may as well count as one. This one's more familiar territory, since it's part of the story-centric point and click genre, but it's still great. Very well written all around.

Papers, Please. Not sure if this counts, since it's not finished yet, but you can play what's already done so far for free. Technically, there's not much in the way of a story yet, it's more about the setting and moral choices, but it's still very interesting and well written. Definitely worth a look.

Look no further: Betrayal at Krondor

Story-driven? Absolutely. Based on the popular fantasy series by Feist and written by Neal Halford, it was so well received that Feist made it canon. The plot is epic in scope. You don't need to have read the books to enjoy it, because Halford made much of the back story part of the game.

Interesting dialogue? Certainly. Every location, enemy, inventory object etc has flavor text which is written in a narrative style. It's kind of like playing a novel. The script is mature and doesn't insult your intelligence - often you gotta read between the lines and put two and two together to figure stuff out.

Interesting characters? Yup. The game is party-oriented and you control a cast of characters, all of which are quite colorful, and most importantly, it's believable that they're together. This isn't a random group of adventurers who met at an inn.

Interesting gameplay? Hell yeah. Almost nonlinear gameplay that allowed you to ignore the main storyline and go explore the game world, which is pretty big, and just find secrets, do sidequests etc. This was quite ahead of its time. Encounters were not level-scaled, so if you were a badass enough player to go to the high difficulty areas as a newbie, the game allowed it and rewarded you accordingly. Combat is turn based and very tactical, and some battles can be really difficult. The game is full of clever puzzles to solve too.

If you do get the game, check out my music/sfx guide.

I suggest Resonance.

Yeah, it's a point n' click adventure game, which is sort of story-driven by necessity; but I found it to be a thrilling, thoroughly engaging and memorable experience.

In fact, I wrote a lengthy review in the subforum on this very website, if you fancy doing yer research.

The Cat Lady - surreal psycho-horror with great story and characters.
Sanitarium - another psycho horror. Strange one and kind of overdoses weird themes near the end (mostly Hive and Village levels), but still - tells a good story.
Gabriel Knight series - paranormal mystery series based on real legends and often real places. Good storytelling.

Mars War Logs - nice sci-fi story with mature writing and good RPG gameplay

Thief 2 - very good stealth missions, a cynical main protagonist, plot twists, conspiracy and a brilliant antagonist

Alan Wake - surreal horror in a beautiful new england setting. Max Payne writing quality, likeable characters and a story which keeps you thinking

darn almost all of my top choices have already been mentioned.

Primordia has a fairly interesting story to it.

Thanks for the giveaway. Interesting thread too, by the way.
Well, that's so hard to answer, but I will try anyway.
According to your advice of avoiding the well known masterpieces, I am going to list, in no particular order, two similar indie games, which are (sadly) not so known and freeware (!).
One shouldn't be fooled by their price, though, as they are, in my opinion, really some little gems.

Mad Father
The Witch's House

There are some other ones in the site you could want to take a look at.

Last but not least, a great gem from the past, playable in modern PC using DOSBox: Shadow of the Comet

Cinders
Analogue: A Hate Story
Inquisitor

I don't know if you'll like any of these, but here:

- John Woo's Strangehold (on sale at Amazon right now)

- The Lost Chronicles of Zerzura

...sorry, can't think of another one, I'll add it when it comes to me.

Count me in for the GA, and thanks.

+1, not in, here's some lesser knowns with good stories:

DreamWeb - Gritty psychodrama, half cyberpunk and half noir. Much enhanced by reading the diary that comes with the game.

Commander Blood - At the other end of the spectrum, surreal science fiction that is often silly, and packed with quirky individualism. Similar adjectives, but less extreme, could be applied to The Journeyman Project series as well.

Bad Mojo - Kafkaesque, literally. Minimal control, lateral thinking, and deeply story driven game where you are a cockroach who was once a man.

Games on GOG with especially good stories include Outcast, Undying, Bioforge, and System Shock 2.