A strong story that unfolds as you play through the game, with events being caused by your actions or you being forced to adapt due to circumstances outside of your control in a believable way.
Level design. It doesn't matter how good controls, targeting, weapons, or graphics are if you're basically running through basic locals and corridors that happen to have a skybox to it. Doom was fine for it's day, but it's never been epic beyond "it was the first big game".
Call of Duty 4, Metroid Prime, Half-Life, these games took level design to be as important as everything else, and we got a lot more out of it because of that.
Weapons. As much fun as a simple Pistol that kills instantly or a BFG to blow up half the planet can be, if they don't fit with the rest of the game it stands out and takes away from it being an epic game.
Replay value, and I don't mean multi-player alone. Have a FPS in which you want to go through it again to see the story in a diffrent way, witness an event (as mentioned before with story) from another point of view and perhaps gain another story path, new weapons that can only be accessed in certain ways.
Imagine playing a West vs East game in which you can only get a certain weapon if you kill a Sniper and take his one-of-a-kind rifle. At which point you can comit an assination yourself or let them go. Have an option to extend the gameplay, create more to the story, and give a nice reward for it.
Co-Op. Playing on your own is fine, playing against others in a death match or against an onslaugh of enemies is another. Playing through a mission that can change depending on what you and your friend/s do? That's something worthwhile there.
Not be the Invasion of Normandy. Seriously, we've been through it enough times we know what happens.
Have James Earl Jones, Patrick Stewart, and Tim Curry voice people.
