QuickTime 6 does come with Sorenson 2 and 3, although it's not the new Sqeeze version, unfortunately. If you want really good compression, get Cleaner.
I've created an MPEG-4 file.
I made the MPEG-4 and also a sorenson-3 from the high-quality iMac ad. I compressed them both at "500kbps", 320x240, 15fps with keyframes every 100frames. The sorenson one had Qdesign music at 48000khz, the MPEG-4 one had AAC at 128kbps. Here's what I found.
The two files had nearly identical quality, with the MPEG-4 having a slight blur (not very noticeable) but the Sorenson was 5.7MB, the MPEG-4 was 1.0 MB. That's a huge improvement.
I also ripped an MP3 and an AAC from a CD (enough acronyms?) at 128kbps and 64kbps, respectively, and the AAC was about half the file size at about the same quality, maybe even better.
MPEG-4 is going to do wonders for Internet video.