Моя первая мысль: у вас может быть проблема с требованиями.
Если одно требование «легко доступно в Windows Media Player», это действительно немного сужает поле, если вы не используете WMP в Windows7 (новые кодеки были наконец добавлены в Windows 7). Вот список кодеков, поддерживаемых в XP (Vista примерно такая же).Кроме того, существуют некоторые ограничения для форматов контейнеров, которые могут еще более ограничить это - WMP в XP и Vista действительно только реально поддерживает контейнеры avi и asf.
В Windows 7 вы также получаете доступ к контейнерам H264 и mp4.
Предполагая, что вы используете Windows 7, ваш лучший вариант - это h264.Вы можете использовать x264, который является наилучшей из доступных на данный момент реализацией кодировщика (он легко справится с указанным вами типом видео), скомпоновать его в контейнер MP4, а затем у вас есть файлы, которые широко совместимы во всех основных операционных системах.(Windows / * nix / OSX).
Если вы не используете Windows 7, я бы сказал, что лучшим вариантом является MPEG-4 в контейнере AVI.