Halo has a very underrated story, due to two things:
(1) People think that it's just another 'shoot the aliens' game with no real plot or backstory
(2) People think the Halo games revolve solely around the Master Chief (a huge criticism of the comics set between Halo 2 and 3 was that the Master Chief hardly appeared in what was considered 'his own comic series', despite the fact that it's been made clear several times that Halo is about more than just the Chief).
The thing is, it actually has a very well thought out backstory shown via (soon to be 4) games, 6 novels, a graphic novel and a comic series, plus the ambiguous Halo: Chronicles with Peter Jackson at the helm. It is about a whole universe of characters and stories and everything is linked, so I would consider it my favourite game story so far.
Another good one would be Assassin's Creed, since the story revolves around what happens in the present day and is larger than the gameplay itself (OK, the gameplay had a few flaws, but it was still a very good game...). It did something few games have done which is to seperate the main story from gameplay (save for the bits where you walk around as Desmond), and it worked, so Assassin's Creed would get my vote too.