There has been a big fanatical rush to get plots into FPS games recently. I thought RTCW had a good balance actually. Enough plot and original levels to make it interesting, with a good hefty amount of mindless violence.
I mean, look at Serious Sam... that game is being praised and it's just DooM with better graphics. Same utterly mindless killing. No plot. Great game.
Half Life had plot, which was worked really well into the game. That was good.
Deus Ex is more of a roleplaying thing, but still had the violence we look for in FPS.
The balance can be struck well, but people seem to be looking for the wrong thing in the wrong place if you ask me.
Just my 2c!