Paint can shrink images, it just doesn't have anti-aliasing, and doesn't support images over 72dpi (if you put one in threre, it will be shown enlarged at 72dpi).

Windows XP's version of paint is a bit different. It supports Jpeg, gif, and other formats, and it kind of anti-alias' things when you shrink them. That is the one I used when I made this picture. (it was originally much larger, using the shrinking technique. I think this one is 50% of normal size)

By the way, I suggest GIMP. For free, it is the closest thing you can get to Photoshop. Moving from paint to this takes some getting used to, though, but the possibilites are quite vast.

To make it easier, if you want to try it out, the windows version can be downloaded here. You'll have to download and run the run time libraries first, then the program. In all, it is 7.84 MB.