Well here it is, I noticed quite a few people demanding the best storylines offered within games in GoG.
Personally I'd recommend:
Beyond Good and Evil GREAT game. Classic. And the sequel is finally being made.
The Longest Journey What can I say?
I'll let others recommend theirs...

Beyond Good and Evil also has a strong female protagonist who also doesn't have to be some super badass chick, and that's rare. Jade is one of my new favorite characters. :D
Sanitarium is a psychological thriller, and one I enjoyed a lot because of the story.

Syberia 1 and 2
Still Life
Great stories. :)

I'll go out on a limb and mention Broken Sword 3: The Sleeping Dragon. Even though the gameplay was pretty much a 3D Sokoban, the characters and story were very interesting, albeit perhaps a bit cheesy.
Apart from that, there's the newcomer Still Life, which sports a blend between modern crime solving and a Sherlock Holmes'ey mystery. I remember I was intrigued by it.
Then there's Psychonauts which has a brilliant and entertaining story as only Tim Schafer can make them. That guy is the Tim Burton of video games.
...and finally, I'll join the choir of Beyond Good and Evil appreciation. It has such an interesting story and lovely characters (Jade, Pey'j and Double H immediately spring to mind)
That's all I can see. Looking forward to see some other recommendations here - I love a good story :).
EDIT: Holy fcking McDingoballs! GOG has Giants: Citizen Kabuto! That game easily has one of the most surreal stories and entertaining characters in any game I've ever played!

The Longest Journey - totally.
Beyond good and evil - great story and great presentation
Original War - it's an RTS with branching story and very interesting indea behind it.
Outcast - Great presentation. Story itself is ... Err ... Stargate, but the presentation is fantastic nevertheless
Prince of Persia: Sands of Time - There ain't much games that have me in tears after finishing them. And even less where I'm not ashamed to admit it.
Betrayal at Krondor - Politics, conspiracies, dirty trics ... What, Witcher and Dragon's Age? Hell no, BaK has it all!
Fallut - main storyline ain't that great, but it'S the stories you help to create that define the game.
Freespace 1 and 2: Because Mass Effect was far from being first
Yeah, that's about it. Only GoG games thou.

Painkiller.

Now that it's possible, anyone care to make a GOGMix based on this theme? ;-)