I just discovered MP4Box (available in osx homebrew as well as other places). It has tools for rearranging your MP4 videos to optimize them for streaming. We just did this on all our videos, and not only do they start up faster on every device, it fixed some devices that refused to play our videos!
Our magic incantation was simple:
MP4Box -hint $file