Ross Mills asks Halo Bible author Eric Trautmann about storytelling in games on Eric's blog:

Q: RPG videogames are well known for their in-depth stories. Without major spoilers, what 5 action games would you describe as having the best, most well-thought out story apart from Halo? (which is cheating, since you did that one's story)

A: Couple points: first, I did not "do" Halo's story; I added dialogue to an existing framework that I did not generate, and second, Halo might not make my top five. The beauty of Halo is not it's story, but in it's scope, and the execution of the storytelling itself.

As it turns out, Halo does not make Eric's list; but the Marathon Trilogy tops it. Read the entire set of questions, plenty of more interesting tidbits in there.