Images, especially in GIF format, compress better when there are long runs of the same colour. If you reduce the number of colours in the image from say 256 to 32 using a handy program like GraphicWorkshop, the image will "suffer" from a phenomenon called "banding." Banding means that large sections of the image will be the exactly same colour instead of the nice texture it should be--which looks worse, but compresses better. Usually it won't look much worse.
Try converting the graphic to JPEG, once again using a handy program like GraphicWorkshop, and compressing at various degrees.
JPEGs work best on "real world" scenes like photographs. For single-color backgrounds GIF files are often smaller and offer better image quality. Screen shots with text are particularly good candidates for GIF files.
Scale the image down the exact height and width you wish to display it at worst. Sometimes you can scale it down even more and let the browser stretch it back out for you. This is iffy because the browser usually uses a very cheap scaling algorithm.
Also, if you don't necessarily need to display the graphic as big as you initially wanted, why not make it smaller on the page?
Crop the edges of the picture to eliminate inessentials.
If you don't need the graphic at all, use text instead. With improved DHTML and CascadingStyleSheets, you can even create blocks of colour. Graphics that are just snapshots of text in the "right font" should be removed anyway because they aren't LynxFriendly or accessible. Don't do that!
You can use the LOWSRC attribute on the IMG tag to display a smaller graphic quickly and then load a larger graphic on top of it later. (Actually, you can do some neat effects with this.) For example:
<IMG SRC="hi-res.gif" LOWSRC="lo-res.gif" WIDTH="231" HEIGHT="107">
lo-res.gif will display first. When the page is done loading, hi-res.gif will load on top of it. This actually transmits more bytes than before, but at least the page will load.
While SVG is unpopular right now, it's likely that in the future most people will have an SVG viewer, as it is a W3C recommended standard. For our goals on this page, SVG has the advantage of describing the programming instructions to generate the image, instead of having the send the entire image itself.
You can often replace a 20K image with a 200K (or larger) applet. The applet won't work on all browsers, and it will require huge amounts of memory and CPU to start Java. You can often tell that one of these pages is loading by listening to the hard drive. (Sorry, I couldn't resist. --CliffordAdams ;-)