The best compression is ultimately judged by the "eye". The human eye can be fooled (actually, the brain), and knowing these tricks can help you edit an Avatar (as I've been inding in the last day or two).
1. GIF - Compression lends itself most effectively to consecutive same-color value pixels horizontally. GIF will store 256 or fewer colors in a palette. The choice of optimization will affect the quality. GIF will be loseless in terms of detail, but lossy in terms of color fidelity. GIF is best used for cartoons, and computer and windows generated graphics. It is generally not best suited for random or real-life type images.
2. JPEG - Divides an image into a checkerboard-like series of smaller squares, and uses a mathematical equation (a discrete cosine transform for us mathy types) to approximate the contents of that chunk. The more chunks, the smaller the chunk and the better the appearance (usually).... but the bigger the filesize. With JPG, you can choose the amount of compression, and compare the result. You should make several test saves, and make the file about 3,5000 to 3,900 bytes for an Avatar (TF limits filesize to 4K). The JPG is best for natual scenes, pictures with not many vertical and horizontal lines (esp. high contrast), and photos. All JPG is lossy... which means the stored result will NOT be as good as the original.
How to reduce size in general? If you are using a GIF (this is generally best for a 65x65 Avatar), then use despeckle to smooth the color transformations. You can also edit the file manually.... I did this with Floppa21's, Becka's, and Ren's avatars in the Site Feedback threads... this keeps sharp detail, yet (esp. in Ren's Avatar of the "Townsville" icon) reduces the storage drastically... in his case, all the blue was changing from pixel to pixel. Once I made all the blue the same color value, the size dropped drastically and then easily met the 4K limit. Becka's Avatar was reduced quite a bit by giving Lime Green hundreds of surrounding pixels. Then I made the Lime Green transparant, and it appears as the Oval-shaped image in the Site Feedback. I did something similar for Floppa's "Smug" smiley, though his Avatar was in no danger of exceeding the 4K limit.
Note: Always save your original as an uncompressed 24-bit TIF("true color"), and edit from that, then save as JPG or GIF when you are done. If you can do it, a PSD (Photoshop Document) is also good as the reference file (lossless). A BMP (256 color limit, though) is OK, if you have no other option. Don't save & edit from JPEGs, however.