Save yourself a lot of time by reading the specs below. I worked countless hours over a couple weeks to try to figure out the best video format for my purposes. I went down numerous dead ends, and filtered through indecipherable gibberish about strange beasts like codecs. Finally, several hints on the Karelia forums led me to stumble upon the formula below, which works really well. Try it out:
I use iMovie to process my video and export the movie using QuickTime. A few people don't have QuickTime, but it's a free download, and offers much more flexibility than the other options. In the export dialog box, click Options in the lower right. Under Settings in the Movie Settings dialog box that comes up, select Compression Type: H.264, Frame Rate: Current, Data Rate: Automatic, Compressor: Medium, and Encoding: Best Quality. Under Size, I use 512x288 on the Original Green site and 560x315 on the Mouzon Design site. This doesn't work with older iPhones, but does work on 4's and on all browsers with QuickTime. The reason for selecting these sizes is because they are my title image sizes used elsewhere on the websites. Under sound settings, I leave all defaults. Under Prepare for Internet Streaming, I select Fast Start.
Two clarifications: People can add QuickTime to any mainline browser, including Explorer, and for free. As for video conversion, you can get exactly what you want in iMovie, so there's no need to convert. In my long effort to figure it out, I got a couple recommended converters, but they were almost useless without knowing all the video jargon I'm unfamiliar with.