Un truco sencillo en Paint que te puede ayudar, es que después de seleccionar la imagen en su tamaño original: le das click derecho->Expandir y contraer y escribes-->50-50 (ancho y alto). Eso redimensionará la imagen dejandola mucho mas pequeña, sin que se deforme la imagen ni se agreguen píxeles de mas. Yo ya lo he hecho muchas veces y funciona. Prueba eso a ver que tal. Y espero que te sirva :)