I'd second Album, I spent weeks fighting with Gallery and found it a tad flakey with large numbers of images. I tried all the hacks and it didn't make a difference. I'm very happy with Album, it's not as easily tweakable (like Gallery) but for me it's fine...

I used to run it under Cygwin on Win 2K on my Laptop and it worked a treat. I've now got a bigger HD so I can dual boot