Wow. I just upgraded to the latest version (1.4.4) of Gallery and it is insanely faster. The really big directories (like my recent Trinidad collection) see the most speed up, especially in the higher number pages. The main page of the gallery is kind of slow right now, but that is because not all of the subalbums have been upgraded to the new album format. It'll get faster in time (I don't want to upgrade them all at once myself, because I want to see how long it'll take them with normal usage).