ICONIA TAB A500はVA液晶を搭載して動画の再生も非常になめらかです。
これで動画を表示するには、最適な映像でエンコードする方法が一番です。

ちなみにうちの環境ではVideo Mastering Works5を使って以下の方法でエンコードしてます。

出力形式 MP4(AVC)ファイル出力

映像設定
ストリーム形式 MPEG-4 AVC
映像エンコーダー x264
プロファイル&レベル BaseProfile@自動(Level3.1)→Highだと動きが激しい場面でコマ落ちします。
サイズ 1280 x 720ピクセル 
アスペクト比率 16:9
フレームレート 23.976 fps
レート調整モード VBR(平均ビットレート)
設定 平均映像ビットレート 2000kbit/sec(画質優先なら4000kbits/sec)
最大ビットレート 10000kbits/sec
処理パス数 2パス 
バッファサイズ 0(自動)
エントロピー符号化 CAVLC
ビデオタイプ プログレッシブ
パフォーマンス 標準

音声設定
ストリーム形式 MPEG-4 AAC Main Profile(Low complexityでも可)
サンプリング周波数 48000
チャンネルモード ステレオ
音声ビットレート 192kbits/sec(128bits/secだと少し音質が悪くなります) 

以上が私のエンコード設定です。
何かの参考になれば

※検証した結果、HighProfileではコマ落ちする場合があったのでプロファイルの説明を変更しました。