Formatos populares e bem suportados em todas as plataformas:
- MPEG1
- AVI (recipiente), XVid ou DivX5 + (codec de vídeo), MP3 (codec de áudio)
- MP4 (recipiente), h264 (codec de vídeo), AAC (codec de áudio)
O MPEG1 deve ser compatível com tudo, mas está desatualizado e tem uma qualidade muito inferior aos outros dois.
O AVI / XVid é muito popular e tem uma ótima qualidade, mas o AFAIK não é compatível com o sistema operacional.
O MP4 / h264 está se tornando o padrão para vídeo em HD e internet, é suportado pelo Quicktime (que garante suporte para todos os Macs, além de um bom número de usuários do Windows) e suporte incluído por padrão no Windows 7.
Eu pessoalmente usaria o MP4, pois ele oferece a melhor qualidade e, se alguém não puder reproduzi-lo, basta dizer "instale o Quicktime" e enviar um link para a página de download no site da Apple.