PNGs are compressed, and you can have 8-bit pngs. In theory, small files will load faster, but I dunno how much the difference has to be to offset the decompression time.

For ultra-small images:
- reduce the color depth as much as possible
- include the smallest possible palette
- convert to png
- use pngcrush with -brute -l 9

Using this on an old copy of Xhenit (automated, so the palettes could probably be smaller), the bmps fit into a 28.1k zip file, the pngs 29.1k. Uncompressed, the bmps take 764k, the png 52.9k.