I don't have a simple answer, except to use lower complexity options like Baseline profile for widest coverage. And use AAC audio, because some devices do not support mp3 or not well. For vod we recommend Expression 4 Encoder for multi-bitrate encoding because of its key frame alignment capability. All the encodes in a set have to be the same profile when you encode with Expression 4, so choose Baseline.
You are asking about the widest coverage, working on the most devices, so lowest common denominator, what works for all is simplified encoding parameters (eg. baseline profile) and aac audio. Just general advice.