mmm I absolutely don't know about the quality of the format, the compression, or the license, but....
what about quicktime movies?
I'm naming them just because in photoshop with the same tool you use for animated gifs you can create .mov or .qt files.
And if it wasn't for the license, I'd go for gifs too, althought the colour limit, mainly because you can have a transparent background and they are very easy to do.
I always thought the licensing problems were only with the compression algorithms, and that there were alternative algorithms, and therefore only the programs to create gifs could have problems, but I may be wrong...I'll read phreak's link.
->well it seem that for all the programs using LZW compression method (it means not only GIFs) must be payed a license, both for compression and decompression, no matter if you are making a non commercial product; I suppose you will have to use this LZW to add gif support wich could lead to some patent violations