Any cheap hosting you would find would run out of space very quickly.
You need to buy or lease a dedicated server. And not just any plan, you need one that will adequately accept and deploy video files.
The security issues would be paramount. Anyone can take a virus, rename it "file.wmv", upload it to your server, then request the virus via the web to hack you into smithereens.
There's really a lot to this. For a programmer, it may be trivial, but for someone asking this question, the only sound advice one can provide is hook it up with an experienced programmer you can trust and HEED THEIR ADVICE.
Even at that, thousands to set up correctly, a minumum of $100 - $125/month for a dedicated server.