A few weeks Michael Heilemann wrote about his search for a gallery solution. And in my wanderings, I have found he is right: there seems to be no perfect solution. If I was dying to do things in MT, I would be looking to study Doug Bowman's tutorial, but since I am not, I won't do much more than admire it. PhotoStack has been my first choice. I think it is largely there feature-wise, it just needs some work done to make it easier to style. The best Flash gallery I have seen lately is SimpleViewer while the best flashy but non-Flash solution is Couloir (check out Photo fades and then some for more information.)
I think the answer might lie in a combination of the last three if I had time to get it done.