I have been making a photo gallery myself recently and I have found a good solution. I consider photography templates from Flashmint quite convenient and usable in terms of a nice presentation and arrangement of photos.
I have read your post and I thought you, Zascar, might benefit from this.