Arcanum: Of Steamworks and Magic Obscura had some EXCELLENT dialog, plot twists, subplots, and atmosphere.
There were so many shadowy little side-stories to investigate. They really fleshed out the world. I mean, not only did the main quest have several major (and well paced) twists, there was also the "X-Files" conspiracy story to stumble upon, and other quests like that. Things that had little to do with the main plot, but were still complex. Made me feel like the world the game was set in was so fascinating.
System Shock 2 and Deus Ex, as mentioned before, have great stories for FPS shooters. The audio logs in SS2 blow those from Bioshock away. And while Bioshock's big plot twist was, in my opinion, alot better than SS2's, System Shock took the plot in a far better direction after the big reveal.
Man just hearing SHODAN say "You. Are. My. Avatar." still creeps me out.