GD does no interpolation on the image when it resizes. If you want smooth images after a resize (like you would get in Photoshop) you'll have to use a more advanced editing library like Image::Magick.
Grr. Thats just the thing. I can't use that because my server doesn't have ImageMagick on their server. I emailed them asking them to install it for me, so I'm still crossing my fingers.