Half of videos on this site ain't really made for streaming. They can only get started once they are fully downloaded. The moov metadata is placed at the end of the video instead of beginning, and so the player has to wait.
To quickly check if video is made with streaming support, you can delete the latter half of a video and see if player can still play it.
You guys are really good at making websites, aren't you? But this is exactly why I like you.
I don't know how easy it is to convert between one and another. If it's cpu expensive, you probably can detect that video is in a wrong format early, and stop uploading, telling the user to encode it properly.