Final Fantasy III
Castlevania III
Super Mario Bros. II
Zeta Gundam: Hot Scramble
Mega Man II

As stated above, Mario Bros. II isn't really a true Mario game... But it is still one of my favorite games to bear the "Mario" title.