Mystery.
Halo was awesome because it was just so mysterious. You would enter a large room on some "Halo" and have no clue what to expect. The Flood weren't even introduced until midway through the game.
Half-Life 1 & 2 were also good because you didn't know what was going on. Aliens entering through a dimensional wormhole, and Half-Life 2 was one long chaotic chase sequence.
Metroid Prime, while a FPA not a FPS, was also amazing because you land on this planet after intercepting a message from a species who saved you and gave you your suit. Yet it's so quiet and barren, half the game you wondered if you would find any living Chozo, but in the end you came a mear days late (last Chozo message states that they managed to beacon Samus and her ship is coming).
Call of Duty 4: Modern Warfare also shares the same truth, you might have expected that the middle east wouldn't get a Nuke, but they did, and the aftermath introduced a lot of questions.