There is plenty of discussion and debate on the in-development and forthcoming (but partially already here) HTML5 standard. It’s much more than native video support, but a lot of the focus is on video codecs, Flash (or the necessity of it), and as with any standard update, the support from various tools, in this case web browsers.
There are many codecs available, with proponents, advantages, and disadvantages of each. I am no expert on codecs at all, but some quick research led me to H.264 and Theora. H.264 is an ITU codec from the Video Coding Experts Group (remember the Joint Photographic Experts of JPEG?). Theora was derived from a proprietary-but-then-freed codec and now developed by the Xiph.Org Foundation.
Of practical concern is the support for these codecs in desktop and mobile browsers. H.264 is supported by Chrome, Safari, and IE9. Theora is supported by Firefox and Chrome. The iPhone supports H.264 (and I assume the iPad does the same) and Android also supports it.
Thus, here is a simple test. Inserted below are both versions of one video in H.264 and Theora. Your browser mileage will vary, of course. I’ve made no attempt to add graceful degradation text for un-supported browsers. The Flash-based playback of the video is on Flickr. By the way, the pixelation and block (compression?) elements in the beginning frames are an artifact of the video itself, not the playback in the browser. I think I need a better transcoder to get from the iPhone video onto the desktop.
You can find more information at the excellent Webmonkey site and their article on embedding video.