Mobile devices are here (Apple iPhone, Nokia N an E series, all different Windows mobile devices etc). All these have two things in common: normal HTML browser and limited display size (resolution). At this moment Gallery2 on mobile device looks awful (too many wrong size pictures on one page with horizontal layout = a lot of scrolling and back-forward browsing which of course is enough slow because of what I already mentioned). For contrast look at Google Reader: on PC screen it is big and usable, and in mobile broser it is small, yet very usable. This is the time to think about some sort of browser and screen resolution detection for Gallery2 too, which should result in correctly resized images, probably on-the-fly (because there are too many different screen formats to store all predefined sizes statically). Show all albums vertically (by that I mean page scrolls only vertically) that no horizntal scrolling is needed and one picture fits in one screen, navigate in some album - show subalbums vertically, navigate in album - show pictures vertically. If it is possible - preload pictures in backgroun, if not - just show fixed number of pictures an at the botom of page there is "nex".
Just a note - this is not the same as WML support, this is for HTML browsers.