SUPER METROID / Nintendo / SNES (1994)
There were non-linear exploration-based platformers before Super Metroid; the first two Metroids, Goonies II, Castlevania II and the NES version of Rygar just to name a few. But Super Metroid has come to form half the bedrock of the Metroidvania genre (along with Symphony of the Night) because it was the first to get absolutely everything right. The games that came before it - prequels included - had begun to realize the appeal of recursive progression, but were either hampered by limited 8-bit technology or just made bad design decisions (or some combination of both.)
The appeal of recursive progression is hard to express; a lot of people play these games for decades and can never really put into words *why* this design style is so appealing. The fundamental appeal of it is actually kind of an exploit of a mental loophole; you chop a game up into small separated segments, and inevitably some of those segments will be duds or irritating, but as long as not *too* many of them are you're golden. When a player hits a segment that isn't particularly well designed, they only half care because their mind is only half occupied with what's immediately at hand. The other half is processing the map as a whole and working out how to unlock its previously impassable pathways. This same phenomenon would be airlifted into Resident Evil (and thus into survival horror in general for some time); it explains why people who really find the phenomenon appealing can put up with the often incredibly jankity-ass gameplay of those games. Recursive progression is actually the driving force behind most traditional adventure games as well, though minus the appealing action twist that keeps you occupied when you're otherwise stumped by a puzzle.
So does that make Super Metroid a fraud? Is it simply exploiting a flaw in our puny hu-nam brains? No sir. Not hardly. You could maybe make that argument for the first 3 Resident Evil games, but not here. First of all, it gets recursive progression completely right. It gives you an auto-map, which I think was the most important new feature by far. Metroid had a strong cult following, but that's all it was until Super Metroid came out in North America and the PAL territories - a semi-obscure cult game, far from being considered one of Nintendo's flagship properties like it is now. I'd make a decent wager that the majority of people who actually completed Metroid on an NES back in the late 80s did so only with the help of the detailed full-color maps found in the Official Nintendo Player's Guide. At the very least, they were laboriously drawing out their own maps on graph paper. These games require you to just mentally keep track of way too much without at least a partial map that jogs your memory, which is exactly what Super Metroid gives you. It tells you where some things are, the really important things, but not all things; it always gives you enough to give you at least a fair clue about where you're supposed to head next when you're stuck. It also stocks the map with plenty of hidden optional goodies like bombs and missile upgrades, giving you at least a small reward even when you find you've gotten off track and explored in the wrong direction.
It's that, and Nintendo Polish. Not every game company has the benefit of Nintendo's dead-on "feel" for 2D gameplay combined with the aesthetic sense (and fairly lavish budget) of their top R&D teams. These powers were brought fully to bear on Super Metroid and with total success. When players get a little stuck, they can at least enjoy rock solid gameplay and a variety of entertaining powers while they wander around sorting things out. That, and great graphics for the time, and a totally spot-on minimalist soundtrack that actually gets how to do minimalism without just resorting to boring ambient sound most of the time.
There's so many more little design details you can talk about, but others have done that already. Super Metroid is one of the crown jewels of the Super NES lineup, if you need the Plato seal of approval for whatever reason.