Both Hunter and Dobralov are right. FPS games SHOULD have an involved storyline (Halo being, IMHO the GREATEST plotline created). However, it's not an FPS without mind-numbing shooting of hostiles. One also has to look at HOW the FPS works. Being a fan of FPSs over anything else, I've spent considerable time contemplating what makes a good FPS, and I've compiled a fair list:
1) Decent storyline - Nothing too fancy, just enough to believe that we're killing the right thing. In BattleFront 2, you kill droids because they're part of the Confederation that you want to re-join with the Republic. The droids are killing clones because their masters believe that the government wasn't truly listening to them. There, a good storyline that explains WHY you're killing something, not just violence for the sake of violence.
2) Good HUD - No gamer wants to be left wondering how much ammo is left. Again, I think Halo had the best HUD of its time, with Halo 2 adapting well to the times. There shouldn't be any stupid looking reticle in the center. We just want a hole to shoot through. If shields are involved, and health ALWAYS is, we want to know how much of either we have left. However, the exception that I allow is Halo 2 because your health regenerates with your shields, almost eliminating the need for the health bar. It'd be nice, but unnecessary. Ammo is important, but we don't necessarily need to know how much EACH of our weapon holds. Just the one we have out is fine. Grenade counters are REALLY nice in an FPS, because you don't want to be trying to throw a grenade when you don't have one.
3) Good, All Around Weapons - Nothing's more annoying that carrying around a weapon you don't want. Again, Halo did an EXCELLENT job of having the right weapons when you need them, and left out the ones you don't need. I, personally, am a short-range specialist. Nothing feels better than blowing something up, or watching your enemy die right in front of you. However, there are those of you out there who enjoy the mid-range weapons, like the Battle Rifle from Halo, or the Pulse Rifle from UT2004 (I probably misnamed the latter). Finally, there are those of you (wimps) who prefer to pick off enemies from afar. There should be weapons for all three weapon favorites (jk on the wimps part). The developers can let you choose what weapon you want to use where, not pick them (oft times wrongly) for you.
4) Sequels, but no Prequels - Almost never in a game can the developer create a sealed plotline that starts where the player starts and ends when the player ends. Most games have sequels, which is good for developers and gamers alike. Developers can make mucho dinero when it comes to a sequel. It's a safe bet that a sequel will sell somewhere in the vincinity of the first game, assuming the developer takes the time to re-write the game enough to be different, but, at the same time, plays true to the previous game. And us gamers enjoy playing a sequel because we already know most of the characters, and don't mind another story (how many stories did you have your parents read to you when you were younger?). What gamers don't want is the same game with the same exact characters doing exactly what they did last time with the same weapons. It's boring to just write that. However, Prequels are mostly nasty. There have been a few prequels that did well (Star Wars Episodes I-III told the story that they were supposed to tell, even with Hayden Christensen and Natlie Portman sucking major ...). But mostly, we've already been told the story, we know what's going to happen to the characters, we know what weapons are going to be developed, etc. IMHO, it's just not smart to develop a prequel.
5) Graphics - Hunter's going to disagree with me, but graphics DO add to a game. The time has come and gone to shoot pixelated monsters that we can't distinguish from ourselfs (Doom...sorta). Deep down inside, we like things to look pretty (Women like to look pretty, men like to look at pretty things). IMHO though, you still shouldn't override a game with good graphics but turn the game into a resource hog. It'll be soon enough when our processors are 100GHz, with 1 Teraflop of RAM. Until then, make the game look pretty, but don't let only those with big $$$ enjoy the game. UT2004 did REALLY well, IMHO, with graphics. Currently (though I REALLY hope to upgrade SOON!) I'm running a Nvidia GeForce Fx 5500. UT2004 looks pretty good, even at 1024 X 768 with shadows turned off.
IMHO, the above should be considered BEFORE making a decent FPS...