First, videos will only upload as fast as the filesize divided by your Internet connection speed. There's nothing that will speed that up other than making the filesize smaller or your connection faster.
What Youtube is saying is that your videos will process faster if they're in a streamable format. MP4 can be a "streamable format" so I believe the problem is that the moov atom is being placed at the end of the filestream. As far as I know, Blender does not have a "Fast-start" option so Youtube must wait until the entire file has been uploaded before it begins processing the video. If the moov atom was at the beginning, Youtube would begin processing as soon as the file began uploading.
[Youtube Link]
The solution is either a Blender Add-On that I'm not aware of or simply use third party software to either encode the video or "fix" the file from Blender. FFmpeg is capable of this. See: "ffmpeg Using -movflags faststart".
@troy_s highly recommends using Blender to render out to stills and then encode with FFmpeg. This preserves video quality and can fix some problems that I ran into with gamma/contrast when uploading to Youtube.
As far as only being able to see 720p or lower resolutions, Youtube processes the video file resolution in ascending order, (e.g. 144p is first, 240p second, etc.) so the 1080p option will not show up for at least a minute or so (maybe longer for larger filesizes) and the 1080p option is not available on Internet Explorer... for me it only works on Chrome.