Ico VS. Wander
Same company, that's all I have really, but it'd be awesome to have them in.
Dovahkiin VS. Corvo
Both from Bethesda (well, Corvo from Arkane, but you get it). Personally, they wouldn't fit in the game, but I would like to see them fight.
Might as well offer my own speculation/ wishlist then:
Cloud vs. Dart - PS1 Era JRPG's.
Spyro vs. Crash - Obvious reasons
Persona Protagonist vs. Selvaria Bles or Disgaea Fighter - Current Gen JRPG characters.
Snake vs. Connor (Assassin's Creed 3) - Because they both involve stealth gameplay and are lone operators on a massive battlefield
Tyrant (Resident Evil) vs. Pyramid Head (Silent Hill) - Iconic survival horror characters
Croc vs. Rayman - PS1 Era platformer characters
Tomba vs. Gex - Well, if you look at it without having any knowledge of either game, it's a cave man fighting a talking lizard.
There are other characters I want included, such as Kat, or the Prince of the Cosmos, but I'm just not sure how the rivalary would work in a funny or creative way.
Speaking about Spike and PaRappa, in the trailer, we can see that PaRappa saves one of the monkeys that Spike tries to catch, and that **bleep** off him... Maybe, in the real history, PaRappa tries to defend the monkeys from Spike, because PaRappa always want to be the hero, or just be a honored man... Obviously, he don't know that the monkeys are working for the evil monkey Specter, and when Spike try to reason with PaRappa, he just don't listened to him
My guess for Cole Vs Raiden is well... When they first started advertising Metal Gear Rising there was this in several of the trailers "Lightning Fast Action"... Get it? Lightning Vs Lightning Fast Action.
Anyway, DLC rivalries.
Patapon Uberhero Vs Prinny (Both have games exclusive to PSP, both are quirky enough to be inlcuded, and could have interesting movesets)