Bueno, yo uso paint, aunque también puedo usar photoshop.
Paint es bastante simple porque de por sí es un programa bastante simple e intuitivo, lo que pasa es que es bastante general, porque no sólo sirve para hacer sprites.
Hay algunos programas más centrados en el spriting, como aseprite, que me ha estado recomendando últimamente Byakuro. Según tengo entendido, es algo más complejo que Paint, pero como está directamente dedicado al spriting, es mejor.
Yo creo que deberías valorar un poco lo que prefieres desde un principio :3