In most cases you will get better results with PNG. PNG has a slightly bigger overhead, so GIF wins for extremely tiny images (with a size about a dozen pixels or less) but after that more advanced compression algorithm in PNG wins.
However, you have to remember to choose the right type of PNG (there is no sense in saving black-and-white lineart as true-color PNG). PNG also may containt chunks of additional info, you can get rid of them too.
Also, there is an interesting PNG8 format which allows you to have alpha transparency with indexed color palette in supporting browsers, but in IE6 it will behave just like gif with index transparency (pixels having any transparency will appear completel transparent). See http://www.sitepoint.com/png8-the-clear-winner/
I'd also definitely take a look at some of the png optimizers. They work by tweaking the parameters of the compression so it's a lossless operation (some of them will do some depth reduction in a lossless way if possible, but that doesn't always bring in better compression). Photoshop has been somewhat well known for not always producing an optimized png.
