I've played with several gallery scripts over the years, and settled on Photopost PHP as being the best.
They keep updating it but I'll be upgrading to the latest version at some point tomorrow. If you'd like to take a look at the admin side, then PM me.

The features I love best are as follows;

Bulk upload of images via FTP and automatic extraction of zipped files containing many images
Automatic thumbnail generation (size selectable) and builds two sizes of image for viewing
Photos sorted by most popular, most recent upload etc etc
Password protection, private gallerys for users, gallery upload file size limits, etc