Se você quiser evitar os Flash players (embora a maioria dos desktops ainda os ofereça) eu usaria:
Formato de compressão de vídeo H.264 com o contêiner MP4. Para cavar um pouco mais, você vai querer um codec de áudio de qualidade com o qual o vídeo, que também é jogável na maioria dos dispositivos, que é o Advanced Audio Codec (AAC).
A principal 'batida' contra esta solução é que ela contém muita tecnologia patenteada. No entanto, dependendo de seus usuários, necessidades e capacidade de licenciar legalmente, uma solução H264 / AAC / MP4 "não deveria" ser um problema.
Outro ponto é que isso não funcionará para vídeo ao vivo. O melhor formato para streaming ao vivo no DESKTOP é ainda FLV (Flash Video com plugin RTMP no player) e para celular, HLS.
Naturalmente, há dezenas de outros formatos para reprodução sob demanda (WEBM, Theora) e streaming ao vivo (por exemplo, DASH), mas você terá grandes limitações quanto a quais dispositivos podem reproduzi-los (se houver).