The last three novels I’ve read have had three stories running simultaneously that join towards the end of the book. Each story has a different main character. I think this may be interesting to use in an FPS game. I believe the important point would be to have three different stories that are clearly linked (maybe not at the beginning) not just three different characters/settings. Each story/character should provide some insight or forewarning about the other storylines.
The books of course don’t normally write from a first person perspective and it may be difficult to adjust each time but if it was part of a well thought out story that required some guess work on the part of the player it may be fun.
Towards the end of the game the player would reach a point where they have to choose one character to finish the game. The main character could then control the other two characters or they each go their separate ways and have slightly different endings, thus encouraging some replayability.
Although not vital to the basic idea, each character could have different skills and abilities.
In some ways you could say that Valve have already done this with Half Life, Opposing Force and Blue Shift. The difference was that they were three separate games, each with different outcomes.
Of course the three characters wouldn’t need to be human, in fact a human, an alien and a robot may prove a good combination. The difference in movement, perception and interaction could be included within the story line giving each character a unique perspective on events.