You've posted a pretty wide open question that has a lot of options. There is a conflict between 'budget' and hosting video - that is if you ever get a sizable amount of hits on your site. Most providers give you X amount of bandwidth to use per month. When hosting video, the likelihood of approaching that limit even with moderate usage increases. The way around this is to host your website yourself and use an offsite source to store your video - like YouTube or Archive.org
(probably better for licensing issues). Then just link to those sites from your own site. This is an optimal solution because the quality of service (QoS) of those sites is typically very high and you won't have to worry about poor streaming or bandwidth limits.
As far as cheap hosting goes, the first place to check would be your ISP. Most DSL / Cable providers offer you web space with your account. Then just buy a domain name and point a CNAME DNS record at the URL to your site. They don't typically offer a lot of space so you'll just be hosting simple html and images there and link offsite to video and large files. You also can't typically install an app like Wordpress or something because they won't offer you a database without paying extra.
If you really need to go out and find your own host I'm sure you'll get lots of recommendations. If you expect to host a lot of video on your own site, then look for a host that has an unlimited bandwidth package - though these may suffer from QoS issues. I've used Dreamhost (LINUX) and WehHost4Life (Windows) and have found them both reasonable for unlimited bandwidth accounts. Dreamhost in particular has a good package that will auto-install Wordpress, Mediawiki, and many other content management apps for you for free so if that isn't in your skillset, that may be something to consider.