At first I thought Gallery2 was just slower than I would expect because of its design. However, a friend of mine pointed out that his Gallery2 setup is running just fine, and I actually tend to agree. Mine has a lot slower 'reaction time' to clicks than his has.
My gallery2: http://gallery.kunsman.com
His gallery2: http://katzedrache.com/pix
Mine is hosting on Dreamhost and his is hosted elsewhere. Notice how much peppier his is compared with mine. Any suggestions?