Metal Gear Solid immediately comes to mind. I've only played the first one, but if the rest are anything like it, then they definitely have some good stories.

Lots of the adventure games from the 90s, especially from Lucasarts, have really good movie-quality stories:

Monkey Island 1-3 (4 was decent, but not as good as the rest)

Sam and Max Hit the Road

Full Throttle

Indiana Jones and the Fate of Atlantis (wish they'd made this a movie instead of Crystal Skull)

THE DIG!

Grim Fandango

Also, Beneath a Steel Sky and Flight of the Amazon Queen were amazing as well.