Прежде всего, у вас также будет звук в ваших видео? Если да, я бы пошел с mp3.
Теперь рассмотрим видеокодек и видеоконтейнер. Я думаю, что вы не должны рассматривать варианты 3 и 4 по разным причинам. Theora действительно непопулярна (я только что натолкнулся на видео theora), а WMV - это технология Microsoft, поэтому ваши возможности немного ограничены.
Теперь о первых двух: я бы пошел с видео DivX (Mpeg4 часть 2) в контейнере Avi. Это действительно популярно, так как большинство компьютеров и множество DVD-дисков способны воспроизводить такие видео. Также есть отличный кодек DIVX с открытым исходным кодом, XVID. Наконец, для кодирования и декодирования DIVX требуется гораздо меньше ресурсов, чем H.264. Последнее важно, поскольку в зависимости от параметров кодирования кодирование H.264 в реальном времени может даже не поддерживаться.
Отсутствие поддержки AVI / DIVX на ряде платформ не является проблемой, поскольку действительно легко перекодировать в любой формат с помощью инструментов с открытым исходным кодом.