Indeed, there are few FPSes with good storylines, not suprising given the genre is essentially action first - shooting and killing lots of things in the first person. In terms of pure FPS HL2 is certainly around the top, but thats comparing it to the likes of Doom/Painkiller/CoD/the thousand games based on the quake engines. If you bring Deus Ex into this, which is heavily RPG as well as FPS, then it can't hold a candle to it.
Ive been pretty dissapointed with the FPS genre in recent times, theres too much emphasis on flashy graphics over substance, the only FPS thats left any kind of lasting impression on me post deus ex was its sequel.
I dont know why I enjoyed Quake 4 so much though, gory fun but not a lot else!