This is happening because mp4 format has its moov info at the tail of the file. The information is required for flash players before the file can be progressively download and play. Therefore if the info is in the end of file, it has to be fully downloaded, which is terrible, user-experience-wise.
From your answer you can compile a separate tool provided in ffmpeg - qt-faststart to post-process the mp4 file and then use the mp4 file for video streaming.
Specially, you can download a copy of source code for ffmpeg, and go to tools folder and run:
make qt-faststart
then you will have a tool named qt-faststart in tools directory. Then you can run:
qt-faststart input.mp4 output.mp4
and put output.mp4 to your streaming folder and the new mp4 file will be progressively downloaded while playing.
Alternatively another option is to do this during transcoding time as suggested in previous answers, but the command line is provided wrong, it should be:
-movflags +faststart
in your ffmpeg command line. It will do the same thing as you transcode.
So there are your two easiest solution to this, hope the best of luck!