I'd recommend starting with 2 & 3 for the NES. The soundtrack might be my favourite of all video games. It has been played by rockers [0] and orchestras [1].

[0] https://www.youtube.com/watch?v=X-WIBmzETBo

[1] https://www.youtube.com/watch?v=9__sJWMXjE0

https://www.youtube.com/watch?v=jdVpJfXXoFI

That's a good question on where to start. I usually enjoy playing games from the classic series because they're simple, but some of the earlier ones can be a bit janky and punishing. The first 6 games are on NES, and they're all pretty good. Mega Man 2 is a lot of people's favorite, and I personally like it a lot but it's not without flaws and some unfair difficulty. 7 was for SNES and I don't care for it much but I wouldn't say it's bad. Same with 8 which was on PlayStation and Dreamcast. 9 and 10 were a throwback to the classic series with an 8-bit art style and can be difficult but they have more modern design sensibilities and I'd say are more "fair". 10 has an easy mode if you're wanting to ease yourself in too. 11 is pretty good too, but has some new mechanics that complicate things a bit.

The X series has some good games, but focuses more on collectibles and upgrades, so you'll likely end up looking up a guide to find where all the upgrades are. It can be very difficult without them. I think X1 is the best in the series, and is also more streamlined than the other games. You can't go too wrong with the first 4 X games. They can be played on the Legacy Collection, but I've heard complaints about the emulation, and I know on the PC version I couldn't watch any of the cutscenes in X4 because they froze. Might be better off just emulating.

Order doesn't matter too much, the plots are mostly disjointed and/or nonsense until the Zero series for GameBoy Advance which are again pretty good but upgrade-focused like the X series, and are less of traditional Mega Man games.

I'd probably just not start with Mega Man 1. Come back to it if you like the series, but it's pretty primitive compared to later stuff.

IMO the 8-bit ones - while fun - are somewhat primitive and often a little too "NES hard". So I'd say start with Mega Man X - it's timeless; still one of the most perfect games ever made.