By default, the gallery short code that WordPress 2.5+ generates looks pretty bad unless you’re using square images, because WP defaults to square thumbnails 125px by 125px in size and creates images that are cropped.
What you need to do is quite simple, but yields terrific results. Go into your dashboard and click Settings. Depending on whether you are using 2.5/2.6 or the new 2.7, you either need to go to the Miscellaneous or Media section, respectively. Once on that page, you need to uncheck the “Crop thumbnail to exact dimensions” checkbox. Unfortunately, this will only affect new images that you upload, since WP creates the various sizes of images when they are uploaded.
Once that is set correctly and you re-upload images, you’ll get a gallery that looks like this and brings you great joy over your earlier predicament. Later on, I’ll be developing more tutorials on galleries, so please leave comments about what you would like to see.