Gif images don't really handle lots of colours weel, however in Fireworks if you choose File, Export preview, and in the drop down at the top of this window select JPG, you should find the quality improves, you can also use the slider bar to reduce the file size, which will show you a preview of how the image is going to look, so you can get it as small as possible though still looking good.
Png files are generaly the file format the applications save the files in, during their editing stage, I think it is best practice to export these files as either gif or jpg, in your case I think jpg would be best.
"Stupid isn't not knowing the answer, it's not asking the question