Acá hay una comparativa de diferentes codecs:
http://www.youtube.com/user/Digigrama?feature=watch
La realidad es que todos los veo bien, siempre y cuando el archivo original esté bien, en la resolución adecuada, al tamaño etc.
En términos generales: sube la versión "más original que tengas". Masticar un video, una y otra vez para recomprimirlo es hacerlo mermelada.