Indiana Jones and the Fate of Atlantis
Legend of Kyrandia have a very good narrative, I think.
Leisure Suit Larry, all of them.
Police Quest, all of them.
Beneath a Steel Sky has a good story.
Alien Breed is pretty detailed when it comes to the story, isn't it?
Cruise For A Corpse is of course a good old Agatha Christie style story.