Warning: This is overkill if you are just playing the video on the phone.
1. Select "iPod Legacy"
2. Change Picture-->Width = 1280
3. Change Picture-->Anamorphic = Loose
4. Change Video-->Avg Bitrate (kbps) = 6000
5. Change Audio-->Mixdown = Stereo
6. Change Audio-->Samplerate = 44.1
(Optional)
7. Save as "EVO 4G 4EVAR!!!!!!111"
Another sample:
http://dl.dropbox.com/u/1138408/Astro Boy-trailer-1.mp4
General thoughts:
1. Max bitrate for EVo is 6000 kbps, so knocking it down to 5500 might make it smoother because at "average" bitrate set to 6000, it might spike above 6000 and make the video stutter a little.