Snake in Super Smash Bros Brawl, back when it was first announced. Not only were they the first guest fighter in that series, they were also one of the less likely ones, seeing how they were mostly considered a PlayStation character, and at the time the upcoming Metal Gear Solid 4 was a PS3 exclusive.
Speaking of fighting game guest characters, Tekken 7 had Negan, a Walking Dead character, Mortal Kombat has recently had a bunch of classic horror and action film characters, Dead or Alive 4 has had Halo and Metroid cameos, Soul Calibur has had oddballs like Darth Vader, and that old X-Men fighting game "Children of the Atom" had Akuma.
Besides that, there are a bunch of weird ones that are clearly advertised up front, but as such aren't a surprise by the time you actually play them. Examples include Kingdom Hearts, Mario + Rabbids, Tatsunoko vs Capcom, etc.







