What video format will play on all Android devices?

Android can play a variety of video formats, but I need to choose one format that will work on all devices.

Do all Android 2.3 devices support exactly the same formats? i.e. if the format will play in the emulator, does that mean it will also play on all hardware? Or do different devices support different formats depending on what decoder chips they have?

If they are all the same then obviously the best format is H.264 at a high bitrate and resolution. If not, then what is the best codec/bitrate/resolution that will play on 90% of devices? Do Google provide some way of querying the device's video capabilities and choosing an appropriate format?