TotalGallery
This script will take care of all your galleries for you, all the way from inserting sponsors randomly to generating thumbnails. It even comes with an administrator part of the site. Each picture has a set of keywords and a category. Users can search for pictures by category or keywords. They are presented with a number (specified by you) of pictures on each page and can navigate through them. The users are shown thumbnails and can then click to view the pictures full size. You could, as an admin, of course set up two modes of operation - a members section whereby they can view the pictures in full size and a non-members section where they can only see the thumbnails. Thumbnails are generated on the fly per your picture which you can upload via the admin part of the site. All HTML shown to users is generated with templates except for a table which is, instead, generated to your specification by a set of definitions in the configuration file.