Here are a few more things from an email from Greg Roelofs about these files:

Delle mentioned that she used Photoshop 4.0 to create the textures, which
explains much of this (large default PNG file sizes). I've never used it myself, but I believe it does
have options to disable interlacing, enable dynamic line filters, and save
PNG images as 8-bit palette/indexed/colormapped files, even though those
aren't the defaults. Setting these options where appropriate will, in most
cases, make up much of the difference between GIF and PNG. More discussion
can be found at
http://www.cdrom.com/pub/png/pngintro.html

...PNG does indeed win over GIF in every case here--although only pngcrush
managed to pull it off with the grayscale linoleum1. The fact that that
file had only 32 levels of gray and relatively sharp edges may also explain
why JPEG fared so poorly, although I didn't check into it explicitly.

Note that in most cases the various command-line tools give essentially
the same results, and what little discrepancy there is can be partially
explained by the presence or absence of certain optional PNG chunks--for
example, gif2png always includes a 39-byte tEXt chunk identifying itself
as the conversion utility. pngcrush looks to be a very useful tool once
it's released, though.

Finally, note that RGBA palettes are an alternative to 16-bit gray+alpha
and 32-bit RGBA (or--egad--32-bit GA and 64-bit RGBA). Generally one
must do a lossy quantization of an image with a full alpha channel in
order to fit it into 256 palette entries, but the instant factor-of-four
compression is often worth it. I hope to release some improved tools for
this in the next few months.