Actually, a BMP can be just as small as a GIF, since both support RLE; the difference is that in practice, RLEing a GIF is the rule rather than the exception, while RLEing a BMP is the exception rather than the rule.