I was thinking about rivals in superhero comics as opposed to video games.
Rivals in a superhero comic really do fight lots. They fight dozens or hundreds of times, right there on the page. It builds up a lot of expectation, a lot of bitterness, and a lot of patterns. On the other hand, your "rival" in a video game generally gets fought at most three times. This is largely because otherwise it gets repetitive and dull.
I was thinking: what if we allowed the players to build their rivalry as they fight?
Rather than fighting your rival dozens of times, what if your fight with your rival included flashbacks? IE, you cut away from the current fight to see a clip from a previous fight, where you and your enemy were both younger, both had slightly different capabilities? What if the flashbacks were actually a controlled element of play?
For example, you and your old mentor are bitter foes these days. The player's first fight with the mentor character has little previous knowledge - just the basic idea that this guy taught you everything you know. That's enough to seed the dialog: "I taught you everything you know, but not everything I know!" "Now the student is the master..."
The first clash will be really basic - the starting abilities of the player and the starting abilities of the master. Probably a more RPG-like fighting system, rather than something too action-packed.
Very shortly thereafter, one of them (the player or the NPC master) will create a flashback by choosing a length of time ago. Then the other combatant chooses an element from an extremely short list with an extremely short time limit.
These two combine into a flashback where the characters are younger, lower-level (usually), and are fighting over something. In this case, it flashes to the two in portrait, slams a quick title "Leaving!? Over my dead body!", and pops up the added powers each has due to the situation. There's a brief voice over to explain the situation while the players absorb the powers they have gained: "I can't stay in the military any longer, sir!" "You can and you will! I'll drag you back by force!" and burst straight into the fight.
In theory, the way the fight resolves will change the history of the character. Getting dragged back into the military is a pretty big difference from breaking free. But the fight is unlikely to complete, at least on this visit. Instead, the two fighters get used to their new power and try to earn some karma points by landing or blocking hits.
When someone wants to end the fight and flash back into the present, they can. The present-day fight continues, with each combatant now having their military combat powers to add into the fray. Both have recovered some of their damage and have additional karma to burn. (Whoever chooses to flash back loses their remaining karma, so burn it fast!)
When either one wants, they can flash back again, either to the same military fight or to a completely different fight. Same "I choose how long ago, you choose what about" setup, excepting if you choose a "long ago" that is already filled by a fight you chose before, in which case you just continue that old fight for more karma and maybe a resolution.
What I'm going for is a kind of dream-like story told piecemeal through a battle. The life story of the characters is well-defined by the time the fight ends (although there may be some mysteries about how certain things went). These characters are then more or less complete and you have a deep appreciation for them, and they can then be thrown into the "final" story (main story) right away.
There are actually some methods for creating arcs that can be adjusted like this.
For example, the master and the hero are not simply random characters. The hero has a friend and a love interest in her past, and they are often thrown into her earlier battles against her master. There may even be cooperative situations, where the master and hero were working together. These are programmed in ahead of time, not arbitrarily created.
Similarly, the hero breaking away from the military and either escaping or being dragged back is not guaranteed to happen, but it is an event whose parameters are programmed in. It affects the plots which happen in the years after that, and therefore affects which other things can pop up in the choices for flashbacks.
Imagine creating your four heroic characters like this, rather than simply choosing stats and skills from a list? You'd go into the adventure knowing their capabilities, personalities, and history. And you'd be invested in them!
... hmmmm, kinda interesting. Dunno whether it'd work well.