Go to Gallery > Options > Thumbnails and you can set the width and height of the thumbnails there. You’ll also probably have the check “Set fix dimension” so that it uses those dimensions for all images.
After you’ve done that, make sure you “Create new thumbnails” under Manage Gallery.
UPDATE: OK, I tested this on my gallery installation, and it only seemed to work on portrait images. I’m not sure why that is – hopefully, this at least gets you on the right track.
