The following idea might be hard because of memory issues, but it'd be really cool if executed well:
You control 3 different characters that are in the same world. You don't control them at the same time; you can switch at any moment to a different character. So far nothing new, right? But actually, each of the 3 characters start on an entirely different part of the game and have their own storylines. So you basically play three game stories with an instant switch system. Now for the cool part: whatever you do with one your characters, affect the world in the game for the other players as well. So it's a really interactive experience, as you not only interact with one game world, but with three game worlds simultaneously.
This could very well work in multiplayer as well. 3 players playing the storyline who each make different choices throughout the game thus affecting the other players playing experience. The game would get a lot of depth both in singleplayer as multiplayer modes.
