I still think Mario 3 could have added blue overalls and white eyeballs to the Mario brothers.
The NES is only capable of displaying a sprite with 3 colors + 1 transparency. Now, you could get away with it with a simple trick where you would split an object up into multiple sprites that each used their own palette line like in the Mega Man games. However, the way the Super Mario Brothers 3 sprites were design, didn't make this a considerable option.
Back on topic here.
The sprites for Mega Man stayed the same most likely because well...they were fine. There was really no need to redraw them over and over again. They represented the character well. In the Mario games, the sprites were redrawn as the developers clearly got more use to the system. Just look at Mario 1 and Mario 3. Big ass difference as they added much more noticeable details to the sprite to better match the artwork. In the case of Sonic the Hedgehog, at least from Sonic 1 to Sonic 2, the sprites had to had a bit of a touch up in order to make room for Tails' shared palette line with Sonic. If they're going to touch up the sprites, might as well improve on the animations while they're at it eh?
Now, while the Mega Man sprites themselves did not change overtime, you should definitely pay attention to the rest of the game. After each NES game, the backgrounds were largely improved, animations for enemies and other objects were much more fluid, and the art design of some levels were now much more colorful than the games before it. Even the boss art improved immensely. Take a look at Mega Man 6. Mega Man 2 doesn't even hold a candle to it in terms of visuals.
Basically, what it comes down to is, if it ain't broke, don't fix it.