Well with your caveat, "must play in iPhone", then the real and only important question is "what is the best video format for the iPhone".
Far as I know, iPhone only supports mp4, .m4v, or .mov. mp4 is good...
But whichever of those 3 you choose, there will be problems in the 4 browsers you listed, not because of the browser but because the browser may lack the pluggin needed to paly the video. Those 3 formats used on the iPhone are not yet that popular, and a large percentage of the Web browsers out there will not have the required plugin.
By far the most widely used video format for those browsers listed is Flash.. but it doesn't work in the iPhone.
However, depending on how much effort you want to put into making your video available to the widest audiance, you can offer both a Flash version and an mp4 (or mov) version and use javascript to detect if there is a Flash plugin... if not, the mp4 version plays. If the browser has the Flash plugin, then the Flash version plays.
Here is a sample page that does just that using swfobject to detect and play the Flash if plugin is available, if not, plays .mov. http://www.cidigitalmedia.com/tutorials/qt/play_qt.html
So you can, in effect, play Flash on the iPhone.
The page also demonstrated how to sandwich Flash between 2 layers of text using CSS z-indexing and declared positions..... that's why the text looks funny.
Best wishes,
Eye for Video www.cidigitalmedia.com
Bookmarks