If you're trying to cover the most amount of devices a mp4 using the h.264 codec is compatible on the all iOS devices and the majority of Android devices (as well as Windows Phone). The "gotcha" area typically is the "level" you set when you encode (see more info at Wikipedia. Older iOS devices don't support the higher levels (and keep in mind that there are now 8 years worth of iOS devices). Current iPhone 6 models support mp4's up to High Profile Level 4.2 (see the Apple specs page for more specifics).
At a certain point you'll need to decide where your cutoff is because you can't support every device unless you go the multi-format route. If you (or your client) is content covering the last 3 years worth of devices, no problem.