The images I use for my gallery are pictures of Japanese calligraphy. The "problem" with that kind of pictures is their dimension: Some are wide, others narrow and tall. Most of the modern, good looking skins I tried tend to crop the images and show just a part of it in the thumbs. But I'd like to avoid that.
An elegant solution that looks tidy and clean would be to have squares (with only a thin border) and shrink the images until they fit horizontally or vertically, depending on their width / height ratio. In fact, that's what jAlbum does in its workspace (see attached screenshot). I'm surprized that there is no skin available that offers this solution. Or did I just fail to find it? Or can it be achieved, for example, with custom code in a skin like Photoblogger or FancyBox? That would be aweseome.
In each case, you have complete control over borders and spacing (all in the settings - do not start trying to code-hack - it's not necessary).
In the other four, non-fixed-shape thumbnails are presented in a justified gallery. They do not crop the thumbnails unless the aspect ratios are extreme, but you can always tell the skin not to constrain the aspect ratios at all. You can control spacing, but borders are limited to 1px.
With non-fixed-shape thumbnails, Tiger also does a "box with thumbnail" layout, with no cropping.
ETA: There, too, you can tell the skin not to constrain the aspect ratios of the thumbnails. Some of your images fall into the "very vertical" category, so you'd need to take control of that. But again, this is all in the skin settings - no need for code-hacking.