More colours = larger file size. Were you using the same background before? That particular bg will chunk out the file. Try it with a plain colour or no background and see what size it comes to.
PNG's are only large if there are a lot of colours.
Personally I hate JPEG, it sacrifices a lot of quality for a minor reduction in file size. As Xuan said it'll either have serious artifact issues or make very little difference. On the other hand though, it's quicker to take a screen dump than wait for the renderer anyway, and then people can have any format they like.
GIF's are better if you can limit the colours correctly and if the program you use is good enough (photoshop make beautiful GIF's, paint GIF's are laughable). The other problem here being that some images need more colours. 128 would probably do for most images though. Alternately you'd have to do a seperate render feature for 64/128/256 colours.
A better solution would probably be to change all the backgrounds to GIF's instead of JPEG, with as few colours as possible- this would reduce the file size of all the backgrounds, fix the renderer (the PNG files would be limited to the same number of colours as the cumulative GIF's used) and ease the drain on your bandwidth somewhat.
---
Dinosaurs had eggs bro, the chicken came way later.