El mejor formato es MP4/M4V con el codec x264/H.264 en vídeo y ACC en audio. Hablo en cuanto a tamaño/calidad. Yo para convertir vídeos uso Handbrake.
De todas formas, otra opción es usar un reproductor que lea todos los formatos, y si además lo hace con aceleración por hardware, ahorras batería. El mejor en esto es el
DicePlayer. Es de pago, pero hay una versión Trial que te dura 3 días para que lo pruebes.
Reproduce todo de forma fluida, incluso más que el MxPlayer o que el propio de Samsung. Hablando del propio de Samsung, también reproduce varios formatos, ¿has probado a ver si te vale sin convertir el vídeo?