Right, so they are already as optimized as possible without losing out on the quality.
In that case, how about using Flash?
Javascript could also be used but I think it would be very complicated.
I think that the way animated gif files work, it just saves each frame as a gif file, and sticks them all together, whereas with flash, you could get the picture to move and it would end up as quite a small file.
You can download a trial version of flash from the macromedia website (
www.macromedia.com) - I think. I personally find it difficult to use, but we have these forums full of people to help you, and there are flash tutorials all over the internet.
Good luck!
By the way, the picture isn't too scary, it's funny though.
As for the brain, that is a transparent gif file. Javascript is used to find out where the mouse is, then a DHTML shadow is moved to where the mouse is. It's quite hard to set up, but you can right click the code and adapt it if you like. The brain picture also has an imagemap so that each click goes to a different page.
Lastly, you are right about lunarpages. A quality host.