For my video server project, I needed to be able to show HTML5 videos in a wide variety of browsers. I also didn't want to have to keep multiple copies of the video in different formats (there were a lot of videos, and space constraints). The closest I could get was using MediaElement.js, which provides a Flash player fallback. You should be able to put an MP4 encoded with the [h.264] video codec on your page, and have it work anywhere. It turns out it's not that easy. (iPads, for instance, need a specific sound codec as well.)
After a lot of research, I came up with the following settings for HandBrake, which will create a video that works (in combination with MediaElement.js) on most if not all browsers, looks good, and has a small size. I've tested it on Windows using Firefox, Google Chrome, and Internet Explorer, on Linux using Firefox, and on the iPad using Safari. If you don't want to enter all of these settings manually, you can download a handbrake presets file instead.