De todos los que he probado me quedo con jetVD, es magnifico. Entras en el programa, buscas el video que quieras, pulsas sobre el y eliges la calidad que quieras, como 3GP, MP4, FLV, y hasta 720p. Cuando decidas la calidad pulsas sobre ella y lo mantienes pulsado 2-3 segundos hasta que salga la opcion de ver o descargar. Lo malo es que creo que no sale en el Market, pero te dejo el codigo QR que asi si funciona:
