My first memories of 'Mario' was Donkey Kong, and I remember playing Mario Bros in the arcades. I never owned an NES, but I played the Vs. Super Mario Bros arcade version.
I remember being underwhelmed by it, but it was likely because I was just better at Defender and Pole Position and therefore got more play value for my money from those games at the time.