Okay, quick update... looked through my Gallery install. In terms of sort order,
you can set a default sort order. In my case, I use chronological or manual, so I didn't remember what the other ones are, but you can also choose
- View Count
So if you want to sort by most viewed as the default, you would set that for the individual photo album. Everything like this in Gallery can be done recursively, so if you want that to be the default everywhere, you would set it for your root album and all the rest would follow barring intervention.
What I don't see right off is how to let the user change the sort order. I'm sure there's some way to expose that to visitors, but I don't see it right off.
As for tags, there's just a module for that and it's probably not active on the demo site
Note: this info pertains to Gallery2. I use that because it integrates with Drupal, but Gallery3 is nearing a beta release (I think it's in the third alpha). The quality of Gallery is such that their alphas are like many betas, their betas are like RCs, and their RCs are pretty much solid. You might explore G3 a bit as it's a faster, lighter, more elegant project - a ground up rewrite with an idea to getting rid of bloat rather than adding features.