That is an actual explanation. I don't know about tiles, but this is the primary reason we can't edit Protoman? Make a tilemap from scratch just for fitting him?
Pretty much, yes.
If you notice, the current Protoman sprite is a 3x3 tile arrangement.
The proposed Protoman sprite is using a 4x4 tile arrangement.
Perhaps by making Protoman's sprite a one more tile taller, we could make a custom sprite for him based on Megaman's so that it fits and is at the same height as him.
As for the technicalities, I am not sure how much work that would be.
I don't know how the code of the game is handled, so I cannot tell if reworking the tilemap for Protoman is enough, or if modifying the sprite loading routine for him is needed.