Are you able to change the encoding?
I get excellent video quality in iOS and Android with basic flv (On2 VP6, MP3, 128 kbps, Stereo) streaming from FMS.
I have not had much luck with other encodings, but I am by no means an expert on the topic, so possibly there is a way to get those formats to work better...
If I use FLV (On2 VP6) video it does work fine. The problem is that I need to deliver 720p video at a limitted bitrate, and when you compare On2 VP6 to h.264 at the same bitrate, the h.264 video looks much better. The client feels that the FLV video looks unacceptably bad.
Ah, yes, I am not serving high-def video myself. H264 is probably better, but my understanding is that you need hardware acceleration to get good performance from it (again, not an expert on the topic, that's just what my understanding has been...)
This document [pdf] may have some usefull info on choosing an optimal encoding for your needs.
(Or you can see the full lecuture here [Adobe TV])