El Galaxy SII soporta varios formatos de video (MPEG-4, H.264, H.263, DivX HD/XviD, VC-1), pero siempre puedes instalar algún programa que soporte más. Algunos traen sus propios codecs como el MoboPlayer, así que puedes usar el formato que más te guste.
Yo, personalmente uso DivX o XviD.
Si quieres aprovechar al máximo la pantalla, la resolución que tenemos es de 800x480, así que usa esa resolución como máximo y obtendrás unos archivos de tamaño más reducido.
En cuanto al programa, bueno, hay muchos, infinidad de ellos. El que te han recomendado arriba, yo no lo conocía y lo voy a probar hoy, eso de que tire de GPU me interesa mucho.
Yo personalmente uso VirtualDub (es gratuito y no tiene mucha complicación), pero sólo soporta como codec de entrada DivX y XviD, así que si tu video está en otro formato, necesitarás un conversor. Total Video Converter es una buena opción para eso.
Saludos.