Gifs are the scourge of the Web. The format uses a patented method of compression and the patent holders are after GIF users. Not only that, but you can only get up to 256 colors in a gif.
The GIF compression method (that patented POS) is worse than ZIP compression, which is used in .zip files and is non-patented and no Unisys fags will come after you for using it.
But there are alternatives. PNG is perfect for stills, and MNG, though not supported well by many browsers, is good for animations.
PNG is a format for still images requiring lossless compression. It can be used for paletted images of 2, 16, and 256 colors, as well as truecolor (up to 48 bits) and grayscale (up to 16 bits). Its non-patented compression algorithm is superior to GIF's patented one. It has okay browser support.
MNG is somewhat like PNG, except that it supports animation. As with PNG, its color support and compression are superior to that of GIF. It also has ways of manipulating the images in a file so that optimized animations aren't so messed-up. MNG's animation is therefore superior to GIF's. On the other hand, only Netscape 6 supports the MNG format with the <IMG> tag. There are plugins that handle MNG, though.
JPEG is used for still images where lossy compression is acceptable. It can only create truecolor or true-gray images, and parts of the image are degraded in the process. However, its compression is superior to either GIF or PNG for photographic images. It has excellent browser support.
For computer-generated or simple pictures, use PNG. For photos or complex pictures, use JPEG.
If you don't mind that your animations cannot be seen by almost any of your audience, use MNG. Otherwise, if you feel that the animation is necessary to your page, use an animated GIF or some PNG's and a JavaScript animation script. But remember that GIF use is at your own risk.