I've always been torn between Graphics Gale and Paint.NET. On one hand, GG has a really great GUI specifically designed for creating pixel art, and it has that really awesome zoom window (for which there is NO plugin in Paint.NET) and built-in AVI exporter.
On the other hand, Pain.NET is great for lots of different kinds of graphics, and has a really shiny GUI with tons of graphical features.
So depending on the sprites you want I'd say it's between GG and Paint.NET. I've tried GIMP but it never caught my interest and all I was left with was frustration.
So it comes down to:
Any sort of pixel-specific art - Graphics Gale
Any other art - Paint.NET