I think I've solved the mystery of the Mega Man icons appearing on the level select screen by finding the game's instructions online.

I beat the first two bosses and got icons. Beat the next two, and no icons. Then, on Knight Man's stage, I found an alternate path to the boss. When I won, I got the "A" parts for some bird weapon thing I believe they called Beat. Then a letter A appeared in Knight Man's spot. So either the blank spaces have the other parts, or the ones with the Mega Man icons do. I suspect it's the blank ones, though. It's all optional in any case, and I think collecting all the letters in Mega Man 5 has the same result.

Anyway, as I said, I finished Knight Man's stage. It wasn't too hard... there was in interesting part where contact with the ceiling or floor causes Mega Man to bounce pretty far. Wasn't hard though, as there are very few things that cause damage in that section. There's one part where a spiked ceiling starts falling on you, but it was too slow to be very tough. Nothing else remarkable about the stage.

Knight Man was tough, though. He's only vulnerable when he lowers his shield to attack, or if you hit him from behind. After losing two or three times, I used Yamato Man's spear attack to beat him. It goes through his shield and causes tons of damage.

This isn't a tough game to begin with, but I think I'm getting much better with the series overall (aside from having trouble with Knight Man). Since all the MM games on the NES are almost identical in terms of control, experience from one helps with the others. I bet MM3 would be far easier for me now than it was when I first played it years ago. I'll have to try that eventually.