For the files on your server you can use qt-faststart, I think they have windows and unix versions. That will reset the meta data to the front of the file.
The second part of your issue might be file size. What is the bit-rate that your encoding your files as ?? We use 6Mb/sec for HD and 3Mb/sec for SD, we also make a 1Mb/sec mobile version which is the one we use for streaming.
Sample file would be 5 min 22 seconds, is 237Mb. That is a 1920x1080 @ 6Mb/sec. The mobile version is 44Mb 720 x 404 @ 1Mb/sec.
You don't really want to stream a HD video to phones, no reason to blow thru that much bandwidth, even if they have a good connection the higher res wont improve the user experience.
