I would love a game like this. Of course we would need a basic plot, but I am sure some random omnipotent dimensional traveller could fix that.
But I do think that a vs. style would be the best. You chose at the begining to side with good or evil, and as you travel the various worlds more people join you. Since FFVII is the most recognizable to the audience, you start as Cloud or Sephiroth.

Only problem is choosing which moves for which characters, and how to link everything together at the end.