I would go with DreamHost at click here.
really cheap, tons of space. All the space you would need for your videos.
A quick guess on what it would cose to set you up with what you mentioned, (not including the Database): around $1000 - $1500. That is what I would probably charge anyway if I had the time.
As far as uploading, what do you mean? Like a upload and others can watch the video, or like sending the video to you?