Colgar un video en un servidor gratuito

Podrías probar con el formato que tiene el video de Winamp gratis. NSV de Null Soft Video
En la página web de winamp hay más info sobre ese tipo de archivos.
Para los demás, se recomienda poner los wmv o quicktime porque son más pequeños y no necesitas un reproductor extra ni codecs para verlos.
Ahora sobre donde ponerlos, definitivamente tendrás que revisar las políticas de el sitio donde quieras ponerlos porque algunos permiten y otros no.