H.264 encoded videos carry their metadata – duration, frame rate etc. – in the so called “moov atom”.

By default encoding programs will insert the moov atom at the end of the video file which is suitable for playback of a local file in a desktop program. However, any kind of progressive download requires the metadata to be available right away for immediate playback. Otherwise the player has to wait for the entire video to be downloaded before playback starts.

Make sure to select an option in your transcoding program which puts the moov atom at the beginning of the file!

In case you already have a lot of MP4 videos with the moov atom at the end of the file, use a dedicated program such as QTIndexSwapper or MOOV Relocator to move it to the beginning.

I would recommend using QTIndexSwapper as it is built on adobeair if your videos will not play straight away and you have to wait till fully loaded then this is your issue.