For what it's worth, I would recommend against GIF.
As an experiment I took both currently available banners, Erethas' and Sarani's, and converted them to JPG with GIMP, after converting them from "indexed" (256 colour) to "RGB" (full colour range) mode.
Results:
erethas_banner.gif 51814 bytes
erethas_banner.jpg 30319 bytes
sarawr-1.gif 54423 bytes
sarawr-1.jpg 16867 bytes
And looking at both sets of images, changes caused by JPG compression were pretty much completely unnoticeable.