If one of those hosts above can run (or perhaps install for you)
Gallery 2 or
Coppermine, those are both very good, full-featured choices. (Personally, I like Gallery 2.)
There's a place called "
pixi.me" that seems to be giving away free Gallery 2 hosting/sites (with some space/bandwidth limitations). I have no personal experience with this site... Anyone else ever use it?