Il faut bien différentier les différentes solutions.
Déjà, deux grosse différence, les sites dynamiques et les statiques, les dynamiques permettent énormément plus de choses, moteur de recherche, affichage par tags, import depuis une interface en ligne, partage de compte...
En dynamique, encore deux catégorie, les services en ligne (tout fait, plus qu'a envoyer ses images) et les script à mettre en ligne soit même.
Les services, comme Flickr (qui est d'ailleurs ce qu'il se fait de mieux), ne permettent pas de customiser l'interface, mais tu as des choses en plus, comme des groupes de partage par exemple.
Pour les script, il faut un espace de stockage, il y en a une grosse tripoté, pour n'en citer que deux, Coppermine et PhpWebGallery.
Ces solutions sont un petit peu plus customisable, mais pour rentrer dans le violent, il faut vraiment bien toucher en programmation.
Ensuite, tu as les logiciel qui te permettent de créé des galeries statiques comme jalbum, ici aussi il faut un espace de stockage, mais pas besoin de configurer le script php.
Le mieux, c'est évidemment les scripts, mais pour l'heure, pas de galerie miracle, chaqu'un a son avantage, il faut choisir selon ses besoin.
Quelques liens avec des scripts :
http://www.framasoft.net/rubrique387.html
http://en.wikipedia.org/wiki/Photo_gallery_comparison (en, mais très bon)