NO estoy muy seguro, pero yo he puesto videos .mpg , .wmv y .avi y no he tenido problemas, a la vez creo son los mas comunes.
tu lo haz dicho hay que ver lo mejor en calidad y tamaño, yo creo k el tamaño es importante ya k no es muy entretenido estar esperando un video k se cargue, y si este demora minutos menos.
En cuanto a insertarlo, yo lo he hecho asi..
<object width="200" height="150" classid="CLSID:22D6F312-B0F6-11D0-94AB-0080C74C7E95" codebase="http://activex.microsoft.com/activex/controls/mplayer/en/nsmp2inf.cab#Version=6,4,7,1112" standby="Cargando fichero..." type="application/x-oleobject">
<param name="filename" value="videos/
tuvideo.mpg">
<param name="showcontrols" value="1">
<param name="showdisplay" value="0">
<param name="showstatusbar" value="0">
<param name="autosize" value="0">
<param name="autostart" value="1">
</object>
Saludos