GIF vs PNG which to use?

PNG almost always gives better compression than GIF, but you need to make sure you're saving the image as an 8-bit PNG. Often graphics programs will save as a 24-bit PNG, which may be why you're seeing the results you are. If you say what program you are using we may be able to advise how to save as an 8-bit PNG.

You can also run the resulting file through either pngout or pngcrush which will reduce the file size even further.

Really the only reason to use GIF over PNG these days is if you need animation.

Apparently png either matches or gets better compression then gif. Try using these tools. The first is from yahoo the 2nd i think i heard about more then once.