What makes a MP4 streamable?

As far as I know, MP4 container files may have their metadata (audio/video tracks, codec information) either at the beginning of the file before the actual data, or at the end. If the metadata is placed at the end, a player can't decode the video stream until it has downloaded the entire thing (unless it can seek through the file, which is e.g. possible using HTTP range requests).

For example, this file has mdat before moov, so it's not streamable as-is:

$ atomicparsley foo.mp4 -T
Atom ftyp @ 0 of size: 32, ends @ 32
Atom free @ 32 of size: 8, ends @ 40
Atom mdat @ 40 of size: 3280091, ends @ 3280131
Atom moov @ 3280131 of size: 139261, ends @ 3419392
     Atom mvhd @ 3280139 of size: 108, ends @ 3280247
     Atom trak @ 3280247 of size: 57400, ends @ 3337647
         Atom tkhd @ 3280255 of size: 92, ends @ 3280347
     ...
     Atom trak @ 3337647 of size: 81158, ends @ 3418805
         Atom tkhd @ 3337655 of size: 92, ends @ 3337747
     ...

See e.g. the FFMPEG "faststart" article.

Additionally (as I just found out), the audio track data can be either interleaved with video data, or not. If it's not interleaved for some reason, the player again needs to wait for the entire audio stream to be downloaded before it starts receiving video data (again unless it can seek back/forward).

See also Fragmentation, segmentation, splitting and interleaving.