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.
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.
Eye for Video www.cidigitalmedia.com