Photo Gallery plugin provides Generated Thumbnail Dimensions option, which determines the physical size of thumbnail images. The option is located in Photo Gallery Options > General page. Thumbnail Dimensions option, which you set when publishing the gallery, defines the display size of the thumbnails.

Please make sure to set Generated Thumbnail Dimensions larger than Thumbnail Dimensions. This is important and necessary for having a nice resolution on image thumbnails. 

After making these changes, please press Recreate button.