Don't you use .PNGs? They're better than .GIFs... .PNGs can be smaller than .GIFs (especially when run through an optimizer like PNGGauntlet) and can have 16 million colours and no stupid compression artifacts like .JPGs do. The only advantages .GIFs have are that they can be animated and that people with ancient browsers can view them - but nowadays everyone can view .PNGs.
My site, VGMaps.com, uses .PNGs whenever possible. You don't want to have to deal with more bandwidth than necessary, so an image-intensive site like mine wouldn't settle for anything less. PNGGauntlet is incredible, compressing some .PNGs to half the original size - but many .PNGs are already smaller than other filetypes.
If you want, I can convert the Mortal Kombat Ninja palette parade banner to a .GIF, but .PNGs are still better!