Los sprites al fín y al cabo son dibujos, y la única forma de crear dibujos es dibujando. Ahora bien, en lugar de usar un programa tan cutre como el paint, puedes usar gimp (el 99% estarán conmigo en que es de los mejores programas para crear sprites). El Gimp es una ayuda sobre todo en cuanto a que tiene capas, de forma que si, por ejemplo, estás dibujando la animación de una persona corriendo, puedes dibujar la base (el torso) que no cambia en una capa, y en otras capas solo dibujas las partes que cambian (como las piernas o los brazos). Incluso puedes dibujar las piernas y los siguientes frames solo son las mismas piernas, pero rotadas un ángulo. Si quieres hacerlo con más calidad, dibujas el torso en una capa, el muslo en otra, la espinilla en otra y el pie en otra, (e igualmente apra los brazos) y luego vas componiendo los frames con estas capas rotadas. En cualquier caso, no es como hacer varios dibujos desde 0, normalmente haces un dibujo base y a partir de ahí vas modificando.

Además te ayuda bastante a la hora de dibujar (tiene montones de filtros, pinceles, efectos de relleno y un laaargo etcetera). Para mí es de lo mejor para dibujar, pero si le tienes manejo al photoshop también puedes usarlo. En realidad son muy parecidos, aunque me quedo con el Gimp.

Otra opción es usar gráficos vectoriales, pero creo que no tiene mucho interés actualmente y complican la programación.