Você quer mover o átomo moov para o começo. Enquanto codifica você pode usar:
ffmpeg -i inputfile [other parameters] -movflags +faststart outputfile.mp4
Se já tiverem sido codificados, você pode simplesmente copiar fluxos sem recodificar:
ffmpeg -i input.mp4 -codec copy -map 0 -movflags +faststart output.mp4
Você também pode usar a ferramenta qt-fasstart. Isso precisa ser compilado no diretório de ferramentas do ffmpeg. O comando é simplesmente:
qt-faststart inputfile.mp4 outputfile.mp4
Existem binários do Windows disponíveis.