I think the best storytelling FPS, besides Deus Ex, I've played was Return To Castle Wolfenstein. That game had a great storytelling method.