You surely need a dedicated server..try the web server section and I am sure you will find some one meeting your requirements.
Will all video sites need this? Thought of trying one out, but if its for say 1000 users will I need a dedi server? I dont want to spend x and y then find out I wont get as many visitors as I need to cover costs. Any way so have a smaler ammount then upgrade to something better if it gets big?
Is this new site? Or where You are right now - at shared hosting? When this is only new site without visitors - then You can start from VPS and then move to dedicated server. Its cheapest way and you know then all ready, what dedicated server you need.
Dedicated is the only solution when traffic inflow is large. You can use planet, singlehop, hostgator