Bueno, la verdad es que para ser spriter no hace falta MS Paint, así que si no usas windows no pasa nada... Con cualquier programa de dibujo que permita dibujar pixel a pixel basta, como pueden ser Gimp (multiplataforma) o Kolourpaint (linux).
A parte del software, para ser un buen spriter hace falta práctica, imaginación, dedicación, etc., como con cualquier arte.
Saber insertarlos en un ROM es parte del RH, y no del spriting.