>Often I'm able to make a smaller GIF than a PNG out of the same image. It might be because PNG is cramming in more metadata, or maybe The GIMP's PNG compressor just sucks.

or perhaps you're not converting the image to indexed mode (Image > Mode > Indexed...) before saving it?
same image (320x320, random data):
test.png: 101 KB (103,993 bytes)
test.gif: 137 KB (141,195 bytes)