I Found out what I'm going to use. My server does have GD, so I am using GD and Image::Thumbnail which uses GD to create the thumbnail. The only part of it that I don't like is that it only lets me specify size=n where n = the longest side of the picture in pixels. I would rather be able to set say the width, and have the side scale down. Any pointers?
Just use GD.pm directly to change the image size. It will let you specify any two integer values for length and width. Try looking into the GD documentation for details.
Update: It looks like you'd want to use the 'copyResized' method.