My impression of the logo was 'turning nothing into something' - I definitely got that from it.

Interestingly, if you DID use Flash I bet you could get that logo down to 1-2kb tops.

The Khoja gallery was just the one I looked at - the point I guess is that the images were a bit top heavy. Optimising them can be done using any one of dozens of free compression utilities. Most graphics packages have exactly what you need built-in - especially Fireworks. I don't think you ned anything fancy (if anything does make out it is 'special' in that respect, steer clear).

JPEG/JPG format is ideal for photos with a lot of detail. You'll find - depending on the photo - that you can go as low as 50% compression with no noticeable loss of quality on the web. A 50% reduction would crush a 500kb-1Mb image down to well under 50kb, I think. JPGs lose their purpose when the photo/image has lots of flat colours, because watermarks will appear.

If you have simple designs (like your buttons and your main logo patters), GIFs are ideal. Cut down the number of colours as far as they'll go (the compression method for GIFs) and you'll get very small files.

Personally, I find GIFs tend to be a bit bigger than JPGs when comparing like for like, but they serve a real purpose.

At the end of the day, if you are happy with it a small degradation is probably totally acceptable since no one will know what the original was like.

__________________
Sualdam