I think games should have excellent, innovative plot, but have some replayability. F.E.A.R. is a good example with its creepy, twisty plot. You could, however, go back and play the game on a harder difficulty level to have your butt kicked. Multiplayer adds a lot to replayability, especially when you get guys playing the game for a while who can totally pwn your sorry n00b butt. Also, open-source games like FS2 and Halo: Custom Edition also add a lot of replayability. But I digress. The best part, IMHO, of a game is the plot. If the game doesn't have a good plot it doesn't find its way onto my shelf. Halo has an excellent plot, FS2 has an excellent plot, Splinter Cell: Chaos Theory has an excellent plot, etc. Overall, if a game's got good plot, it's a good game right there. But, what makes an excellent game is replayability. The three greatest things that make me want to play a game over and over again are:
1) An extremely hard difficulty level. Most of the reason I replay a game is to see if I can beat the game on the hardest difficulty level. Both Halo 2 and FS2 take the cake on difficulty.
2) Open-Source Engine. Gearbox and Bungie released Halo Custom Edition to the PC Gaming community. Dark Hunter and I both love to play the custom maps made for Halo because it adds to a game we already love and desire to play as much as we can. Freespace 2 was Open-Source as well, and you guys can see how well that did for Freespace's replayability.
3) Ironically, the plot. I love hearing, and as Dark Hunter will attest, memorizing game lines. And it's fun to see the characters go those cool moments we all know, love, and obsess over (at least I do, right Hunter?). A good plot will actually have me playing the game on easier levels, after I've beaten the hardest level, to try different tactics and see how the plot differs.