Is EC2 really only ~370,000 instances overall? That seems off by several orders of magnitude...

There's certainly better quality codecs out there, compared to 1.0. Take a look at the work happening now on 1.1, though, it gets very competitive:

http://web.mit.edu/xiphmont/Public/theora/demo5.html

The bitstream format was frozen, not the code.