For sprites I just use good old MSpaint. You can use the eraser tool to do a single color over the entire sprite set at a time. Right-click with the mouse and swish over the entire thing with the eraser - it'll change the foreground color to the background color, and nothing else.
For battlers I'd probably use GIMP or the like.