It's a tough question because it depends on a lot of things. Basically, think of it as the users connection being the limiting factor. On my mediocre DSL line, everything under 8Mbps loads fine, anything higher than that will stop to buffer once in a while.

So basically I recommend thinking about who is gonna watch your videos and when. If your target audience is people living in the future with fiber everywhere, then 4K is fine. If you want shitty public McDonalds/Hotels wifi to buffer, then even 720p won't be enough for them.

You could also upload a SD version, then the HD and link to the SD in it.

Video Encoding is a tough challenge, I'm still unsure how it will be done in the end, but something needs to be done. Right now it displays the bitrate on the upload page as an indicator, but maybe I will just force a maximum bitrate in the future to prevent bad uploads.