I have been reviewing various galleries on social networking sites, with your question in mind.
The first thing that comes to mind when I see your examples is that they all have to much unused space that should be used for images.
Use a navigation tree on the left, and recent images on the right. The navigation tree would cater to those who want a category structuring. Those who do not want this would simply turn off the navigation tree. Consider to use GWT.
The right side of the page would have images only. No text, no categories, only images. Hovering could show title and category. Showing a small round icon in the image, depicting the number of comments would be a nice function I have seen here and there.