First of all, FPS games used to be my favorite along with flight sims. There are 2 shooter games that I can think of off the top of my head that really stood out to me. One was Half-Life and the other Thief.
I loved Half-Life not just because of the gameplay, but because of the way they incorporated the story into the game. I'm not one for enduring much text or chat in my FPS games and I thought they created a great balance that let me feel like I was never too far from the action. Plus the game played like you were reading a book. I HAD to find out what happend next! Swinging a crowbar was icing on the proverbial cake.
Thief on the otherhand wasn't so much about story for me as it was about great game mechanics. Your main weapon was a bow and arrow and if you pulled the string back for too long you began to shake and aiming became problematic. Also, you had different types of arrows like water arrows to put out torches. And an indicator to tell you how visible/audible you were to the guards. That game literally made my palms sweat I'd get so into it.
I could go on but that's the short version. :)