My favorite story is from Planescape: Torment. Not only is it a deep story, it gives the player choices that are far deeper then most games with choices (like all of them).
I've never played Planescape: Torment, but I did play Baldur's Gate,
I and
II. As you probably know, they recently rereleased the pair, and they announced last month that they're rereleasing Icewind Dale (and probably Icewind Dale 2, it only makes sense).
You can bet that Beamdog will rerelease Planescape: Torment as well!
And I'm going to play it.
As for my favourite storylines in games, I'll make a list of plots that stood out in recent years, in order of best to next-best:
1. The Last of Us
2. The Last of Us: Left Behind
3. Half-Life 2: Episode 2
4. Mirror's Edge
5. The Dark Eye: Chains of Satinav
EDIT: And how could I have forgotten Portal 2? Portal 2 gets a place here as well — above Mirror's Edge, below HL2: EP2.
And as for old games with amazing plotlines:
1. Baldur's Gate
2. Baldur's Gate II: Shadows of Amn
3. Dreamfall: The Longest Journey
4. Final Fantasy IX
5. Final Fantasy VII
6. Final Fantasy VIII
(I actually prefer VIII over VII, but VII has a stronger story, in my opinion)
7. The Legend of Zelda: The Wind Waker
(I refuse to put OOT or MM because they have very little story to speak of)
8. Fire Emblem: Path of Radiance
9. Halo: Combat Evolved
(Despised the rest of the Halo series, but I have fond memories of the first installment)
10. The Elder Scrolls III: Morrowind
(No, not Skyrim)