Well I hope every character has a different rival, because if it doesn't, we'll probably have to fight every rivalry twice, once with a character, and once with the other, to get two different endings... That would be annoying.
Also Paul Gale said something like "A's rival is B, but B's rival is C, and C's could be A"
Cutscene explaining how character got into this universe -> Rivalry is established -> Rivalry is overcome -> Boss is introduced an related to the character -> Boss is defeated -> Cutscene explaining what happens to character after the events
Obviously with a couple of other match ups between other characters in between. Hopefully it won't match the length of MvU3 arcade mode, that would just be lame.