It's a very interesting, and intruging concept to have a different story based on gender. What may be a more straight forward approach, yet still what you want, is have the chracters be actual people in the game, IE, what R,S,E did, but better. Have one Main story, with 2 arcs in it, one where the Male is doing something, but at the same time, the female is off doing her own thing. It would make sense chronologically speaking, as you are playing as each character, and the opposite gender character would be off doing their own thing while you are doing your own thing. The problem that lies in that would be the player getting lost in the story, and not connecting to the player character.
But rather than having 2 different stories, it would be very interesting to see a game with 1 story, but two sides of it, if you will.
Just a thought.
