Hola John.
He descargado el video al que haces referencia (Sin problemas con los pop-ups y en 10min.)
El video se ve (con permiso de los moderadores) que te cagas, el video es de los que mejor se ven dadas sus caracteristicas.
Lo que hace que el video ocupe tan poco espacio, es el Bitrate, 280 Kbps. y el codec AVC.
Pero hacer videos con ese Bitrate y que se vea bien, se necesita que el video master sea de mucha calidad,
Este video en cuestión por el logo (KBS2HD) se ve que es HD, mínimo 1280X720 con un Bitrate que no bajara de los 6000 Kbps.
Luego probar con varios programas y codecs distintos, ya que para unos mismos parámetros, hay diferencias notables de unos programas a otros, y ni que decir de los codecs.
No se decir un programa concreto, que te de el resultado esperado a la primera.
Empieza con los más sencillos como
SUPER © ó
Format Factory
Suerte.