If it is mp4, then you need to check what codecs are used. iPhone usually encodes everything in h264, however, there are different profiles of h264 and high profiles might not be supported on Android, because they are more complex for decoding.
Even apple says in their documentation:
H.264 Baseline Level 3.0, Baseline Level 3.1, Main Level 3.1, and High Profile Level 4.1.
iPad, iPhone 3G, and iPod touch (2nd generation and later) support
H.264 Baseline 3.1. If your app runs on older versions of iPhone or
iPod touch, however, you should use H.264 Baseline 3.0 for
compatibility. If your content is intended solely for iPad, Apple TV,
iPhone 4 and later, and Mac OS X computers, you should use Main Level
3.1.
Baseline profile should be played everywhere.
See the list here - http://en.wikipedia.org/wiki/H.264/MPEG-4_AVC#Profiles
So if you have control over encoding (if the video is recorded from your iOS application), then you can do it programmatically. I just googled and found a piece of code where the profile is set: http://forums.macrumors.com/archive/index.php/t-1512924.html