My very first Metroidvania was Blaster Master. And then maybe Faxanadu (if it can be counted...maybe not). I didn't play the original Metroid until a number of years later.
But Jesus H Christ, I love the Metroidvania genre. It scratches my gaming itch so perfectly every time. Oh, and I do consider the first two Prime games to be Metroidvanias. Sure, it's 3D, but the underlying exploration and progression is classic Metroidvania. The third game is a little different since it's got multiple planets.