Phex there is two separate issues here, firstly the codec involved. It either is or is not installed on the machine trying to play the video, it is not a browser issue. There is nothing that fits that bill universally. MPEG1 probably comes closest. It will play out of the box on most Win, Mac and Linux machines. I should note I don't know how much phones are compatible with MPEG1. Something tells me they aren't going to be and isn't going to phone friendly because of the larger file sizes. Even on slower connections it isn't going to be very friendly, it requires 4 to 5 times the bitrate of modern codecs.
Assuming the codec is installed you need to get it to play nice with the browser, there really isn't any universally accepted way for this to work. If you check around you'll find some HTML code that comes close but there is an endless loop of issues. With HTML5 there is going to be a standard so there is some light at the end of the tunnel.
Until then the only real solution to insure most people can view your video is using a plugin. Flash and Silverlight both eliminate the codec and browser compatibility issue.