For the Marvel vs. Capcom series, we've got Shuma-Gorath and Marrow. Predating all of those (back in X-Men: Children of the Atom) was the Sentinel, which surprised some as Sentinels are Mecha-Mooks rather than an individual character. Jin Saotome from Cyberbots had Americans asking, "Who the hell is Jin?" and "Isn't he from Tekken?" Also, few were expecting Strider Hiryu and Captain Commando to make a reappearance after about a decade in the doldrums (though the former would go on to be a series mainstay).
Nova was also a highly unexpected addition, compared to the rest of the new additions. Nova had never been a big name Marvel character, with his only major claim to fame being he was Marvel's Alternate Company Equivalent to Green Lantern as the resident Space Police. Not long after, however, he would appear in Ultimate Spider-Man (2012) as a SHIELD agent, perhaps increasing his visibility for some. However, the Nova in that cartoon was not Richard Rider but instead a Canon Foreigner named Sam Alexander (though Sam's Nova costume would be made available as Nova's alternate costume as an Early-Bird Cameo). This was likely an attempt to promote a potential appearance in Guardians of the Galaxy (2014), though he was cut from the final film.
Even more so than Nova, Rocket Raccoon was on paper a very surprising inclusion with almost no one having heard of him outside of comics at the time. However, it is quite possible his inclusion was there to promote the upcoming Guardians of the Galaxy film which would release the following year. The fact he would also appear in the second season of The Avengers: Earth's Mightiest Heroes (which aired right around the same time) alongside the rest of the Guardians, complete with the same voice actor (most of the Marvel voice actors in the game were Role Reprises from that cartoon), also lends credence to his inclusion in the game being to promote the film.
After his franchise was ignored by Capcom for so long, no-one was expecting the very first character in Marvel vs. Capcom: Infinite to be Mega Man X. Jedah joining the series as a new character was unexpected as well, not just given how long the series has been dormant, but considering other Darkstalkers characters like Felicia and Demitri have made more appearances than he has.
Street Fighter X Tekken includes Poison (who was never playable in the Street Fighter series before), "Bad Box Art Mega Man",note Capcom had planned several other Mega Man games for release that year but ended up cancelling all of them; this Mega Man was supposed to be a gag addition to the release schedule and was received as something of an insult as a resultPac-Man in a Mokujin robot, and exclusive to the Sony platforms are Cole MacGrath and Sony Japan mascots Toro and Kuro. And while Akuma as the Street Fighter side boss was hardly surprising, nobody expected Ogre to be the boss for the Tekken side.
Capcom's choices for their own representatives in Tatsunoko vs. Capcom seem to come from the far corners of their character library. For Street Fighter III they went with Alex (a very slow-paced character in his source series and one whose moves don't spring to mind in a hyperactive fighter like the Vs. Series is known for, though it is worth noting that he was supposed to be the new focal character in his game to complement Ryu) instead of someone more nimble (such as Ibuki or Necro). From Onimusha they pulled Kaijin no Soki, who only appeared in Onimusha: Dawn of Dreams, as opposed to Samonouske Akechi, the protagonist of both the original and the third game Demon Siege (and ostensibly the "true" protagonist of the series). Saki Omokane, from Quiz Narairo Dreams, might have some presence to Japanese audiences but American players would only know her as that girl with the rifle who can be chosen as an Assist Character in the first Marvel vs. Capcom. And finally they pulled a Lost PlanetVital Suit to represent their "giant" character opposite Gold Lightan, tagged "PTX-40A" and helmed by an unseen pilot. No characters from Resident Evil or Devil May Cry made the cut.note Although Nero had been considered until the limitations of the Nintendo Wii made creating adequate representations of his Devil Bringer attacks infeasible. Dante would mark the series' first appearance in a Capcom vs. game with Marvel vs. Capcom 3. And the Big Bad is, of all possible people, Yami, the final boss of Ōkami, who is already a Giant Space Flea from Nowhere in its own game, and no one else from Okami is in this game. For the Updated Re-release, Ultimate All-Stars, Zero is an understandable choice (who is famous for his Laser Sword and having previously appeared as a fighting game character in SVC Chaos) but Frank West once again comes across as an unusual pick (albeit he is the most prominent cast member of his franchise, having appeared as the playable protagonist three times in the original game, Dead Rising 2: Off the Record, and Dead Rising 4 - although at the time of TvC he had only appeared in the original game, making his character less prominent than it became later). Both of them would also return to the Capcom vs. series in Marvel vs. Capcom 3 (Zero in the original Fate of Two Worlds and Frank in that game's own "Ultimate" Updated Re-release with a heavily modified moveset) and Marvel vs. Capcom: Infinite.
Capcom Fighting Evolution features four Red Earth characters, none of whom are Tessa. note She previously appeared in Super Gem Fighter/Pocket Fighter and SVC Chaos: SNK vs. Capcom, herself an example of this trope.