The GIF patents expired while Firefox was still in early development. And it was not the GIF format itself which was patented, but a particular compression algorithm used with it -- decoders, as used in Mozilla, were not patented.
People could (and did) create uncompressed GIFs to avoid the patent risk. For obvious reasons, uncompressed H.264 is not useful.