The “Handy Command-line Video and Audio Conversion Commands” article has been updated to include the ffmpeg command and arguments needed to create baseline videos recommended by mobile devices and, I believe, required for at least some Android devices.
We struggled a fair bit to figure out what was needed to get video to play on Android 2.3, but as it turns out, while the command listed on this page for creating baseline videos yields playable files in some cases, this seems inconsistent. Judging by a number of reports it appears that Android 2.3 is just mired in video compatibility issues that few can fully address and account for in some coherent manner, so some sort of banner warning about these compatibility issues might be a good idea. Video support in 4.x seems much better, for now video issues in 2.3 appear to be unresolvable. I’m unsure if hypothetically even if video compatibility in 2.3 was flawless whether video playback would be consistent without random stuttering and/or serious battery life drain. General Android performance seems to be an issue addressed most recently in the 4.x series.
Creating baseline versions of your videos seems to be an idea commonly recommended, if nothing more because they are more bandwidth and resource friendly.