I don't have an android phone yet. I have a pre. But I do Video work for a living and as a serious hobby.
Several methods to convert videos exist. Some good ones are free, some EASY ones cost money.
Here are the details that I KNOW will work on ANY modern mp4 player (iPhone, Pre, iPod, Android, etc.) Convert your videos to an MP4 file with the following settings:
720X480 resolution. h.264 codec, baseline 3.0, stereo aac 128 kbps.
Here are several programs that work from cheapest to priciest:
XVID4PSP 5.0 R90 (again, use the iPhone preset and don't use version 6, it's still in Beta and NOT reliable)
-FREE
Arcsoft Media Converter Platinum (use the iPhone II preset, or Nexus1)
-$50 1 time purchase
DVDFab DVD to Mobile (Same iPhone preset)
-$30/year
There are many others, but these three are VERY consistent in quality and good speed in conversions for non tech-heads. These presets are NOT the highest quality the EVO can play. I'll post a tutorial thread once I get my EVO and have a chance to see the highest quality/bitrate it can handle without skipping or freezing.
For those more adventurous, here's the settings I'm using based on a best guess:
mp4, h.264/x264, 1280X720 23.974 fps, 2,000 kbps, baseline 3.0, AAC stereo 128kbps, SubpixelME:7, ME: MultiHexagon, Deblocking -1,-1. (If you don't know what these mean, use presets until a good tutorial [mine or someone else's] is put up.)