It depends on how you look at things. To me, there are two main schools of FPS thought: ALL THE GUNS, and ONLY TWO GUNS. Of the former, I would say that UT2004 beats its competitors in both variety and engagement of combat--yet it has barely any semblance of story, being mostly just "here's some background, just go shoot things." Not that Doom, Quake, or Wolfenstine have particularly engaging stories, but remember that Half Life and HL2 are "ALL THE GUNS" FPSs, and they have a fantastic storyline (at the expense of its combat.)
Of the latter, Halo and Halo Reach have, bar none, the best combat, but they do fall behind the pseudo-RPGs like Bioshock and Deus Ex in terms of story. On the other hand, Deus Ex/Bioshock/etc. have so much else packed into them that they don't really feel like FPSs to me.