I'm also looking for a good but clean gallerysystem for two years now, so here are my thoughts of what I would consider ideal (to my needs anyway):
1. Multiple galleries, also sub-sub-sub galleries if needed (like: "animals" => "cats" => "mickey" => "asleep"), displayed as thumbs or textlinks.
2. It would be nice if the images would be saved in the same manner on the server, in differently named folders (would be easier to delete them when deleting a certain category of images.
3. Gallerypages with the option of a certain number of columns and thumbs per page (max. longest side, so the images always have the same proportion: 125x80 or 80x125 px) with short name/description beneath them. Paging and breadcrumbtrail on top of page.
4. Clicking on one of the thumbs to display the larger image in a popup to keep in 'contact' with the thumbnailpage and avoiding unneccessary scrolling in case of larger images.
Personally I don't need al that exiff information or comments from viewers. Just a clean and quick way to browse through images with as little 'garbage' around it as possible. And integrated inside my wordpress <div id="content"> of course. :)