Encoding video for mobile devices?

MadGeek007 writes: I am developing at app for Android that will use many short (averaging 10-20 minutes) instructional videos. Unfortunately, I know next to nothing about encoding video. I'd like to use a codec that is supported by Android and iOS out-of-the-box. I need the videos to look decent on large mobile displays (IPhone 4, HTC EVO,etc), and still be able to stream well on a good 3G connection. The sound quality is also important. With so many different display resolutions on mobile devices, do I need to encode multiple copies of the same video? Or can I get away with a one-size fits all video? Can anyone recommend encoding software, codecs, resolutions, and bitrates that would work best for this?