Agreed--it depends entirely on what you're compressing for. Some things are designed for low-bandwidth use, others are great for uber-quality. That's why there are so many formats.
Now, if you're talking about the standard "good quality in a reasonable amount of space" type of compression for videos and that sort of thing (the 240X320 - fullscreen size range, bitrates in the 100-300K/s range), then the choices are slimmer.
The current choices for best quality are probably:
Apple-style MP4 (actually only one of the video compression codecs available in MP4)
DivX
XviD
3ivx
Sorenson 3
As I understand it (though I'm far from an expert) DivX, XviD, and "MP4" are all now accepted parts of the MPEG4 spec (3ivx might even be, too). They're all fairly similar in terms of potential quality, though, and use similar styles of compression. I think (not positive) that new versions of any of those codecs will work on the others--if you've got the DivX codec installed in QuickTime, you can watch XviD video, for example.
In my personal experience, it's sort of a toss-up between MP4 and XviD; I believe XviD is theoretically just a royalty-free version of DivX, but I've managed to get far better quality out of the free version. Apple's MP4 compressor seems to produce better color at the cost of slightly more noise, but that could just be Apple's compression scheme.
As a Mac user, I'd highly recommend MP4--it's built into Quicktime, Apple's compressor works quite well (especially if you don't set it to constant bitrate), and it's fairly compatible with other systems. AAC audio seems to have poor support on Windows outside of QT, but I'm not sure about that.
XviD might be a better choice for some files though; it's supported by a lot of PC video players, and it will play just fine on a Mac with the proper codecs installed.
There are freeware XviD encoders on the Mac, and ffmpeg supports it quite well.