The first Mega Man I played was Wily's Revenge on the Game Boy. Pretty tough up to the point that I hated it. Thank god there were passwords, so I could at least take a glimpse on the boss weapons and the Dr Wily stage up to the point where you had to fight four bosses from Mega Man 2 (NES) in a row.
The first MM I've beaten a few years later was part two on the GB. It was fun!
The cheapest way to get into MM and MMX now are the two collections on the PS2, both can be had for 10 € each in unused condition. The emulations are fairly faithful and thus enjoyable, apart from MM7 and 8 on the anniversary collection. Good thing the last two are not my favorite games anyway. The collections come with both password and save features, even for MM1 which lacked passwords back in the day.