Originally posted by Blick

GIMP
PROS:
Essentially a free Photoshop. With even more roundabout ways to get stuff done. It's said that it can animate, but I never figured it out. I couldn't even figure out how to mix my own colors. I only ever used it for tracing scanned drawings.
CONS:
Developer's wet dream, artist's nightmare. AKA one hell of a confusing program.

Paint.NET
PROS:
I've never used it, but I hear it's less powerful than Photoshop, but better than most programs out there. My guess is that it's somewhere around Graphics Gale level.
CONS:
Never used it, never heard any complaints. Mustn't be too bad.

Graphics Gale
PROS:
Layers, animation and little stuff like right click as an eye dropper and palette indexing, I think. Basically a better version of MSPaint.
CONS:
Scrilla for registering.

Giffy
PROS:
Really simple .bmp/.gif converter. It's pretty helpful to have if you're like me and pixel in MSPaint only. Supports transparency, which is always a good thing to have.
CONS:
None.

EZtoon
PROS:
A simple animation program that's good for sketching up rough animations. Has flood fill dithering too.
CONS:
1bit, hard to find (exactly why I'm hosting it...).

UnFREEz
PROS:
Easy to use drag and drop animator. Just grab each .gif file and put it in.
CONS:
If you want to edit the animation, you have to remake the sequence, each frame has to be the same timing, you need a seperate .gif file already in existance for each frame.

MSpaint
PROS:
Bundled with Windows, easy to use, pretty much perfect for pixel art with the grid, up to 10x zoom (click the lowest responding line of pixels under 8x and it'll go to 10x), grid for those that can't tell if they're placing pixels evenly or not, optional preview window.
CONS:
Can't save to .gif very well, doesn't have: layers, opacities, alpha transparency (or any form of transparency for that matter). So basically just good for making static bitmaps.