Your mom.

Uh, MS Paint or photoshop.

Graphics Gale

It has served me well.

And I don't make .GIFs with it, so I don't need to buy the full version.

I had problems with Graphics Gale on Vista - windows didn't look right, and stuff was funky. I uninstalled it until they come up with a better version.

Unintuitive like Blender, or just unintuitive like suddenly trying to use Windows 3.1 again?

The blood of small kittens

(it really adds to the artistic effect, sometimes I include a part of my ear)

I found the interface in graphics gale really handy. I haven't seen any bugs, other than the animation preview has some weird frame rates sometimes. Probably more to do with my computer than the program, though.

Also, once you adjust to using the right-click-as-an-eyedropper feature, it can do wonders for small, animated sprites.

I think it was this one.

On topic: I'm not allowed to say, because it's not freeware.:P

Are you trying to scale an 8 bit aka paletted aka 256 colour image? In that case, convert first to RGB (24 bit), then scale.

Traditionally, a drawing program which displays an image "zoomed out" will use a linear interpolation as it's not too slow. You can check it by drawing a pure black and white image : When zoomed out, if it displays grey pixels to smooth out the edge, it's one of the interpolation modes (bilinear, or bicubic).
Your problem is strange, because if you choose a scaling mode in the menu, the program should just apply it...

Sometimes you get a better visual effect if you apply some smoothing before rescaling, but it really depends on the style and size of the image.

This is virtually impossible: You cannot scale pixel images without any loss of quality - when you scale the image down, you lose information, because the resulting image has less pixels; when you scale it up, you need to 'invent' pixels that weren't there before, and depending on the type of image, you need to choose a suitable scaling algorithm.

IIRC, GIMP lets you set the on-the-fly scaling mode to any of the 3 (aliased, bilinear, bicubic), and when you resize, you can select a mode independently.

However, bicubic is not always the best option; images with sharp edges (such as pixelled art) may 'overshoot' around the edges, and bilinear is often a better alternative.

Another thing GIMP may be doing is using 3d hardware to do the on-the-fly scaling (that is, upload the image as a texture and then render it as a 3d quad using OpenGL or something like that); in that case, the scaling is done in hardware, which is faster, but doesn't necessarily match the software algorithm that GIMP uses for the actual scaling. Typically, 3d hardware uses trilinear filters, that is, produce a series of mipmap levels, and then use 3 stages of linear interpolation: two for x/y and one for the mipmap level.
If you are scaling down by a factor of less than 50%, then you may consider applying a 50% scale iteratively until you can reach the target size with a scaling step between 100% and 50%; this somewhat approximates the mipmap algorithm used by graphics hardware.

Which paint application doesn't?

The tiny little Artist's Sketchbook doesn't. No wait, it does! With rocks, actually.

Gimp 2.4.6 is very stable for me under windows xp, they have changed how it installs on windows, it comes with its own set of gtk+ libs, instead of using the system install of it. So it has helped with stability heaps, but I have a gtk for pidgin (that was my setup choice, so it could have a different gtk skin), and one for gimp, then the system install.