Hi Blossom Welcome to WebmasterWorld [webmasterworld.com] :)
This old chestnut eh? You've hit on a problem that's been troubling web designers for many years.
Firstly you have Internet Explorer's (IE) deficiencies to support, then you have large gap in file size between PNG's with alpha transparency and GIF's with index transparency.
Here's the deal with IE(6)—it doesn't naively support alpha transparency—so you can use either index transparencies for your PNG/GIF—which allows either totally opaque, or fully transparent parts of an image... or... you can use a PNG with alpha transparency allowing translucent aliasing (seamless integration with its background). However this route will need the IE6 PNG Transparency Filter hack to ensure IE6 users do not get horrible black blobbing.
Regarding image size - how big is your PNG? Generally speaking, as you've recognised, you need to keep your file sizes as low as possible, but broadband take-up world wide is affording us a little more freedom... Check your logs, are many of your users on dial-up?
Would it be possible to use an index transparency GIF that's been created with the background it is sitting on in mind. So the dreaded jaggies are hidden? In other words - mimic aliasing so to the naked eye it looks like it's seamless.
