Ваше первое препятствие - получение приложения на реальной платформе. Единственным вариантом, если не считать прямого контракта с Microsoft, будет платформа Indie / XNA. Игры XNA не могут подключиться к Интернету. Так что забудьте эту опцию.
Если вам удастся набрать комплект разработчика и заключить контракт с Microsoft, вы увидите варианты h.264, wmv, avi и даже divx. Вероятно, существует больше форматов (re: Containers), которые будут зависеть от кодека, но первого должно быть достаточно для любых нужд.