I started out using minigal – version b13 – it was a pretty good program, one that I thought I would end up using on my website. In the b13 version, you were able to upload your photos to the server and then save them in different folders. It was a cool program. In the newer version – minigal2 – the developer changed the program and now all photos must be uploaded to one folder only. Having to store 3000 photos in one directory folder sucks. So did some of the developers answers in his forum when he was questioned about that change.
Simple PHP Gallery is a great little program except that, if I recall, you cannot spread thumbnails across several pages. If you have 100 photos in an album, then all 100 thumbnails are displayed on the same page. If the ability to spread thumbnails across pages was added to that program in the future, then I would use it in a heartbeat.
I am currently using Coppermine – impossible to integrate – but faily easy to get it to mimic your existing website layout. But the program is certainly overkill – more features than I need – but it had most the features that I wanted. However, their support staff in their support forum has a couple jerks who enjoy degrading people more than they do helping them.
Creating a photo gallery looks like something that the greater majority of wordpress users want to do – and it also appears that a large majority of them are not totally happy with the solution they are using for their gallery – so it would make sense in the future to spend some time developing a feature in wordpress that you allow you to do just that. The developers were able to introduce the page feature in 1.5 and did a fine job – why not have a built in galery feature as well. WordPress would then be greater than it already is.