The Witcher's story, atmosphere and English voice acting were superb. It might be the best RPG I've ever played. When the Witcher 2 comes out, the original deserves a place on GoG.

That said, the combat was mindless, once you figured it; cool looking, but mindless.

Gabriel Knight.

Wait there, Betrayal at Krondor has a downer ending?

I wasn't expecting that... Is it happy-sad or just plain sad?

Also, is Return to Krondor a direct sequel or is the plotline mostly unrelated (e.g. just using the same world)?

As for Beyond Good & Evil, it is clichéd and, at least from what we got to see, pretty simple, but it was so superbly done that I didn't mind. I hope they make a sequel, the story was screaming to be expanded!

Other than that, I'll just go with the crowd and say The Longest Journey. I also loved the sequel, but not everybody did. I hope they finish it.

Vampire The Masquerade: Redemption has got a really good story

The Longest Journey for best told story and Sanitarium for uniqueness. Longest Journey is the better game though.

Psychonauts has witty repartee between the characters and lots of cool ideas. The actual story arc is just alright, but the way they fill in the pieces with crazy sets, kooky characters, and funny dialogue is great.

I agree that BG&E's story is a bit basic, but it's well executed, and Jade is a fantastic lead character. The OP seems rather action-oriented, so Psychonauts might be a better choice than some of the point-and-click adventure games.

Having said that, I think the Syberia series has an excellent blend of story, characters, and atmosphere (in a low key kind of way); and Still Life has one of the most brutal (brutal, not graphic) scenes I've ever seen in a game right at the climax of the story. I was really impressed when I played through it.

PoP: Sands of Time is good fun--again, more action than story, but the characters are great.

What are you guys talking about?

Clearly, the game with the most compelling story on GOG is Blake Stone: Aliens of Gold. The scathing criticism of unrestrained big business turns into an emotional downward spiral as the character of the game becomes less and less interested in stopping evil and more interested in stealing the wealth for himself, ultimately buying into the system of greed he was sent to stop.

It's either that or Redneck Rampage, the most insightful examination of The South since the works of Flannery O'Connor

QFT.

Planescape Torment! Oh wait... :)

Okay, kidding aside, Arcanum has a pretty epic story.

ROFLMAO!

Arcanum has a very interesting story, but it's not epic.
Advent Rising has an epic plot, very interesting.

Edit: I mention also Outcast

By all means do not skip a great game just because of somebody's opinions, by the time I had played Baldur's Gate myself for the first time, I just felt like it (storyline) had been seen too many times, but I did enjoy the journey thoroughly.

Well, the good thing about a great story is, the plot itself doesn't really matter. The plot gets rehashed millions of times, and has since the dawn of time. Plot is what you're able to describe without involving any characterization. Plots for a lot of great games are very similar, as was mentioned in this thread about a number of games. Namely, you're the chosen one, or the fish out of water, and suddenly you have to save the shop/neighborhood/world/universe. That tells you absolutely nothing about the story though. The story is about the characters, their growth (or lack thereof), their decisions and reactions that move the plot forward.

Plot is basically what happens, regardless of your characters: you're a doctor who has to stop a vaccine from going to market because it turns everyone into rage monkeys who only listen to pop music and kill people for wearing sandals.

Story is what happens when you put a particular character in that situation: you're a grizzled old doctor, a reclusive expert who'd rather get sent case files than deal with actual patients. Then one day, a case so bizarre comes across your desk you have no choice but to see the patient. You grow attached to the patient as they turn into a rage monkey, and start to become attached again to humanity as you race to outsmart Rage Monkey Co.

That's the story. That's why Jade's adventure in a very simple plot in Beyond Good and Evil makes it worthwhile. You have interesting characters in interesting places, and the plot is just an excuse to escape into an adventure using them as your vicarious avatar for a while. It's not a masterpiece -- more like an exceptionally well done Saturday morning cartoon -- but the ability to tell a story, to even have a good story, is still a developing area of games.

Sanitarium is a mind screw on the level of Philip K. Dick.

King's Quest VII is like an adventure thought up by the guy who wrote Alice in Wonderland

Syberia is...difficult to explain easily. It's like a watered down version of the serial adventures that Indiana Jones was based off of, but still manages to be fun.

I agree, but I also haven't given up hope of finding a game with a good story and a novel, intricate plot.

Daedolon, based on nondeplumage's post, would you say that Baldur's Gate actually has a good story, but an overused plot?