Photoshop is great for anything pixels.
Illustrator is great for anything vector art, although there are cases where I prefer Inkscape, mainly when the SVG-ness of SVG is important to me.
I'm a creative programmer, not an artist, but all the artists I know also use Photoshop. The Gimp has some nice programmability, but it's just … not … right. It's making moves in the right direction, but it has such a huge deficiency to make up.
You may also want to consider modeling your art in some 3D tool, and use rendering. The later 2D pixel-based RPGs (before they all turned full 3D) used that workflow to generate the pixels. Model 3D, animate walk cycle, render out from all the direction you need.