In nearly 20 years of gaming, one would think I'm qualified to tell what is a good story or not.
How so? Most games aren't known for having good stories, you know...
As far as story goes, I think Silent Hill 2 and 4 are worthy of some praise.
Modern (as in post-V) Final Fantasy games typically have pretty decent storylines, but also have some god-awful moments that keep them from being great.
Metal Gear Solid 4 was enjoyable story-wise, but was also totally absurd and overdone. Lots of great fanservice perhaps, but not a great story.
Assassin's Creed series might be up there. I haven't beaten any of them, so I don't really know how well the stories progress as you get farther along, but they all start off very intruigingly. Combined with the lovely environments that are ripe for the picking, and I bet the stories in Assassin's Creed are pretty damn good.
The Mass Effect trilogy has been pretty damn amazing story-wise thus far, even though ME2 was basically a side-story and I'm a little unsure about how well ME3's story is gonna pan out.
Some older games that had stories I thought were awesome back when I played 'em but don't really hold up would be Perfect Dark and Hybrid Heaven, both for the N64. Both are crippled by the fact that they're trying to tell stories in a very cinematic fashion with in-game cutscenes, when the hardware just wasn't at a point to make such an approach successful. Perfect Dark is the worst out of the two, mainly because it's story gets downright silly towards the end.