Even the simplest image-editing utilities let you play around with bit-depths and other compression settings. Photoshop 7 and Fireworks MX both offer superb interfaces for previewing and managing compression options. Controlling color tables, dithering, and transparency while you fine-tune an image's size is a breeze with these two titles.
Photoshop has other options for power-users wanting better control over the image compression process. With weighted optimization, you identify important areas in your image using a masking tool, and then vary the compression settings across the image's different regions. For example, you could apply maximum compression to the background of a candid snapshot, and apply better image quality to the people in front. Your finished product shows people's faces without any strange-looking digital artifacts, while the unremarkable background contains evidence of higher compression settings.
Weighted optimization works on GIFs, too. For instance, you might mark off key aspects of logo artwork, so critical image areas wouldn't dither or have colors jump, when you began adjusting the bit depth.
Nifty, eh? Well, to quote every self-respecting TV infomercial, "Wait! That's not all!" There are other Ginsu-sharp tools in Photoshop's "Save For Web" dialog. One is a blur effect for JPEGs that reduces the impact of digital artifacts most handy, but best used with a light touch. Photoshop 5.x and above also let you specify JPEGs to be formatted as "Baseline Optimized", which is a slightly smaller format file size-wise. Disregard Photoshop's warning that Baseline Optimized JPEGs are less compatible they look OK in all browsers. Well, except of course for Lynx.
(Alright, alright. Since you really want to know, baseline optimized images use different quantization divisor tables and Huffman dictionaries than specified in the old-school JPEG/JFIF standard. So while optimized images may throw some image-editors and encoding software for a loop, the JPEG decoder in a Web browser doesn't care, since it parses the DQT and DHK markers to get those tables! Yeah, like, I know, how wacky is that?)
Obviously, JPEG compression relies on extremely advanced mathematics. GIFs on the other hand...
A GIF is just a list of colored pixels. GIF's only attempt at compression is to abbreviate whenever same-color pixels are right next to each other horizontally. And that's all.
So with a row of 100 white pixels, the GIF format saves space by using an annotation along the lines of "one white, 99 more of same color". A row of alternating black-and-white pixels, on the other hand, requires a more verbose description ("one black, one white, one black, one white") and soaks up more space. Basically, it's a big deal if colors change on the same horizontal line.
Photoshop 7 does have a "Lossiness" feature for decreasing GIF sizes, which takes advantage of GIF's fondness for like-color clumps. Photoshop will substitute pixels here and there, and try to increase the number of same-color pixels sitting next to each other. It works okay, but not as well as it sounds; the automated results can look pretty bad, especially on the types of pixel-perfect artwork you'd want to use GIF for, anyway.
If you're hell-bent on optimizing a GIF's size beyond reducing its colors, consider the compression scheme while designing it, and avoid changing colors along the horizontal axis. E.G., if you were drawing a logo with a "black-white-black-white" checker pattern in parts, consider using a solid grey instead. Don't forget, GIF compression only takes horizontal rows into account. Ten vertical lines of white pixels occupy as much space as ten vertical lines of ten different colors.
Bad GIF pattern
Good GIF pattern
Wow! I think we finally have compression covered.
Executed by an expert (that's you now!), this increased control over image optimization should squeeze a few more kilobytes from each of your images, saving users seconds (and hopefully minutes) when paging through your site. That's charitable, but remember: when a user doesn't feel their time is being wasted, they're liable to do just that waste serious time. When they do it at your site, clicking link after link, that's a good thing.