Super Mario Bros. 3 by Nintendo, released for the NES in 1990 (2 years earlier in Japan) and a whole year later in Europe.
Super Mario 3! Most folks will tell you that this is their absolute favorite game on the Nintendo. Most, if not all. Me? I will always prefer the original SMB, but it's hard not to love this iteration. There's so much to do, and so many turtles to kill!
Mario 3 was a huge breath of fresh air and it came out at such a perfect time during the 8-Bit Nintendo's dominance. There was already an avalanche of excellent software for the system, and Mario 3 was the new king. So much thought, care, and love was put into the design of this experience. Everything looked, sounded, and played great. Also, the game was long, it was challenging, and it was very addictive - you just kept coming back for more. The only place they really dropped the ball was that there was no save-feature, you had to play all the way through from the word GO.
Mario 3 introduced so many elements to the Mario platforming genre. Power-up suits, P-Switch blocks (switching coins to blocks and vice-versa), power-up suits with unique powers (hammer suit, raccoon suit, frog suit, Tanuki Suit.. Riot,) a giant world map with very fleshed-out world themes, boss battleships.. Things like dungeons, bonus-life minigames, hidden secret shortcuts and boss battles were also extrapolated on. It was a very tight package.
Mario 3 has enjoyed a stellar legacy possibly more than most of its' brethren (I'll still argue that it can't touch the longer-reaching influence of the first SMB). It's also a game so well-designed that it absolutely holds up to play even today. Definitely a classic.
It's trite to mention it, but games like this and it's ilk (Mega Man 2, Metroid, Castlevania) were absolutely what kept Nintendo head and shoulders above its' competition in the 8-Bit days. These titles really blew away the higher-tech arcade machines as well, despite their simpler looks they were just much more deeply playable. It was a Golden Age of Gaming the likes of which we will never experience again (of course, it helps that I was still early in my teens..)