One major factor to note: the 5 color PNGs are size-equivalent to the 4 color GIFs. If you're really serious about maximum image quality for minimum size, PNG looks like the way to go... but I'm not terribly familiar with the image format, so I'll let the entries speak for themselves:
THE FOUR COLOR ENTRIES: Compression die-hards. They not only chose a superior but obscure file format, they decided black was optional...
PNG - 7150 bytes
Fireworks - 4 color
I hear Dave actually reduced the height of the image by two pixels...
PNG - 7214 bytes
Paint Shop Pro
convert the black borders to blue
Ulead SmartSaver Pro with the following settings:
Compression Method: Median cut
Web Snap: 0
PNG - 7431 bytes
reduced image depth to 4 colours
saved as 4 colur PNG
PNG - 7551K
Start at 8 colour gif.
Snapped all colours to websafe.
Select 'remove unused colours'.
delete non major colours (leaves 5).
Changed the black colour (borders on countries) to the same blue as labels
PNG - 7584 bytes
Convert to image->mode->indexed. No rastering, optimal palette with 5 entries.
Open dialog "indexed palette". You see that we now have the following colors:
*light blue for the ocean
*red for some text
*dark blue for the remaining text
*green for land
*dark green for land boundaries
Click on the dark blue field, then select the Hex Triplet value (#02027c), copy this value with <ctrl-c>.
Click on the dark green field, select its Hex Triplet, and paste the blue value there with <ctrl-v>, then hit <return>. The previously dark green field is now dark blue as well.
Close the palette dialog.
Convert back to image->mode->RGB.
Convert again to image->mode->indexed. Still no rastering, but this time with an optimal palette of size of 4.
Save as PNG. Deactivate all options in the PNG settings dialog, use highest compression (9)
PNG - 7638 bytes
set it to about 15 colors
filtered by hand down to 4 colors
PNG - 7770 bytes
(1) menu > export > png
(2) drop to 5 colors
(3) replace black w/ dark blue, leaving four colors
(country borders are still visible, just not as dark)
PNG - 7847 bytes
Paint Shop Pro
reduced the image painstakingly to only 4 distinct colors
changed some pixels to create longer 'lines' of a single color & removed dark blue border
exported in png
THE FIVE COLOR ENTRIES: Staying true to the original... Black lines intact.
PNG - 8089 bytes
converted to indexed image with 5 colours
saved as PNG with level 9 compression
no interlacing, no transparency / gamma etc
PNG - 8747 bytes
Saved as png8 with 5 colors