Ogg Theora looks interesting.
The free, patent-unencumbered video codec now works in over 24% of the world's web browsers with no plugins required. The latest 1.1 release of the Theora encoder is coming out any day now. And when it does, the huge improvements in quality and functionality made over the past year with support from Wikimedia and others will percolate out into the major GNU/Linux distributions, arriving at the fingertips of those who build and maintain the world's biggest video sites.