Nick’s Photo gallery allows up to 5 columns of thumbnails. You have 4 columns. I am afraid that increasing that to 5 is your only option to make thumbnails smaller.
I’ve noticed that some of your thumbnails do not load fully – like in this Bilbao gallery (see screenshot).
Sometimes, they finish loading on page refresh, but not always. This is caused by too big file-size of each thumbnail. You should consider using separate image files for thumbnails and for display. Images for thumbnails should be much smaller in dimensions and in file-size than display images.