What codec is used for .MOV files, then? As far as I know they can only be en/decoded by Quicktime.

MOV files have used dozens of different video and audio formats over the years. Currently, the most common is H.264 video and AAC audio, and they can in fact be played by nearly everything, mainly because the MOV format is basically the same as MP4. You might have to remux the file though, as there are some subtle differences between MOV and MP4. Yes, this is yet another reason to hate Apple.

Cool -- so if I start distributing H.264 videos without paying the appropriate licensing fees, there wouldn't be any trouble, right? And there's an encoder/decoder that I can install legally?

"Proprietary" has a very specific meaning in the multimedia format world; it revers to formats like Real Video, VP6, and so forth which are completely closed. In other words, there is no public specification, nobody can implement an encoder or decoder without reverse-engineering it. If you want something to describe H.264, say "patent-encumbered" or similar; don't misuse words with a specific meaning.

Obviously you've not used Theora for months or years. It is significantly better than MPEG-4 SP, and on par with H.264 for standard-def video.

I've read the spec. Here's the basic summary:

1. Prediction. DC/AC coefficient prediction is somewhat similar to MPEG-4 Part 2. Intra prediction is similar, as is motion compensation, which is basically the same as MPEG-2/4 halfpel except that the center position averages between the diagonals instead of all four neighbors, which is slightly lower quality but much faster (a smart decision, H.264 does the same for qpel). 4MV mode is supported in the same way as in MPEG-4 SP.

2. Transform is basically the same as MPEG-2/4, though it's bit-exact like VC-1's and H.264's in order to avoid decoders disagreeing on the correct output. It's slightly slower though because of how On2 originally designed it.

3. Entropy coder is bizarre but not too terrible; it should probably give results similar to MPEG-4 SP's entropy coder, though I can't be entirely sure just because of how weird it is. Speed-wise the entropy coder is a real problem, especially for hardware implementations. The reason for this is because every single data element is coded in a massive bitplane, requiring that the entire frame be decoded before a single inverse transform is done. This requires a cache larger than the decoded size of the frame itself, as DCT coefficients are stored in 16-bit precision as opposed to the 8-bit precision of the actual pixels. It's probably fine compression-wise though.

That's for residual coefficients though; the primary problem in terms of compression with Theora is the motion vector coding...

3a. Motion vectors can be coded in three modes: "use the previous vector", "use the previous previous vector", or "write an entirely new vector". The last mode requires writing 12 bits of raw data with no compression; X and Y vector components. The problem with this is twofold. First of all, it means you can't have motion vectors longer than 16 pixels, which is crippling for high resolutions. Second, it means the motion vector coding is actually worse than H.261 (the original standardized video format from 1988); Theora probably loses at least 10-30% compression solely because of this. It would in fact simplify the specification to fix this, which is why many have been pushing to revise the spec and release a "Theora 2".