書き出した動画がカーナビで再生できません。

>「ビデオ」と「オーディオ」タブ以外で変えてみるべき箇所はないでしょうか。

互換性に関するものとなりますと「マルチプレクサー」が影響するかもしれないのですが、デフォルトの設定（MP4, 標準）で問題ないようにも思います。一応、PSPやiPodといった選択肢をためしてみるといかがでしょうか。

あとは、私が添付した画像では縦横比を16:9にしていますが、これを正方形ピクセルに戻したり、キーフレームの間隔を15くらいにしてみる、オーディオのビットレートを下げてみるなどの方法もあるかと思います。

個人的に再生できたファイル仕様のビデオストリームの「MPEG4 visual」というのが気になるんですが、

AVCからこれに変える方法は何でしょうか？

書き出しの際、形式を「MPEG4」にして、マルチプレクサータブでマルチプレクサー「MP4」ストリームの互換性「標準」を選ぶと、そのようになると思います。

2番目のご返信で「再生できたファイル」の仕様にあります「シンプルプロファイル　レベル1」では、解像度が大きく制限されてしまいます（720x480では、MPEG4の規格と矛盾しているようです）ので、レベル3でお試しいただくと良いのではないかと思います。