What's going on with MS Paint is that you've set it to use only 16 colors. Thus, when you import a picture onto it, MS Paint is going to find the closest color, pixel by pixel. I you can have a way to set it to 256 colors or even "millions of colors," they should look a lot closer to the original sprite.