Sonic the Hedgehog 2

From SmashWiki, the Super Smash Bros. wiki

Sonic the Hedgehog 2 is the second installment from the Sonic series. The game sets Sonic on his second adventure. It's also where Tails makes his debut. In this game, Robotnik tries to thwart Sonic again but fails.

[edit] In Super Smash Bros. Brawl

Tails, who originated in this title, can be seen in the background of the stage, Green Hill Zone. In addition, the music for the Emerald Hill Zone can be heard, unaltered, in Super Smash Bros. Brawl. Plus, Super Sonic, Sonic's Final Smash, made its first appearance here.