What About PNG?
The PNG (Portable Network Graphics, or "PNG's Not GIF") format
When Welch created the LZW compression algorithm, he was an employee of Sperry Corporation (later purchased by Unisys). Sperry was awarded U.S. patent number 4,558,302 for the invention, and hence the LZW compression method belongs to them (at least in countries that recognize software patents).
When CompuServe first developed the GIF format back in 1987, it didn't check for the LZW patent, and claims to have been unaware of the fact that the compression algorithm was the property of Sperry/Unisys.
Around the beginning of 1995, Unisys contacted CompuServe, and they issued a joint announcement that they would start charging developers a license fee for software that created GIFs.
By this time, the PNG file format was already being developed and was ready for implementation within weeks of the CompuServe/Unisys announcement.
The PNG format can compress using lossless or lossy methods, can handle palettes of any size, and will make an excellent replacement for GIF, once it's ready.
The PNG format has many features that make it superior to GIF:
No patent problems
Support for small and large palettes
Better transparency, with alpha-channel support
The reason I cannot recommend PNG for immediate deployment on most Web sites is that there are still many browsers that are not equipped to support images in the PNG format. Also, PNG does not support animation, and of the browsers that do support PNG, few support its transparency features.
I consider it unfortunate that the most popular browsers are now all owned by huge corporations that don't have any motivation to implement a superior graphics format, even with a complete reference implementation available free from the PNG developers! But alas, they don't. And until they do, if you use PNG files on your site, you will loose viewers.