Видео - это значит высокие нагрузки, а => простой хостинг за 300 р/месяц не подойдет. К нагрузкам можно отнести перекодировние видео на лету и т.д. Тебе нужно либо арендовать выделенный сервер, либо ставить свой. Думаю, что на первое время можно арендовать, так как если дело твое двинется, то можно всегда пересесть на свой сервер. Хотя у тебя могут быть проблемы с трафиком. 1/4 - это требование хостеров, если я не ошибаюсь. Так что думай. А по поводу того, где арендовать сервер, то тут хоть agava хоть masterhost.
P.S. Прошу не кидаться кирпичами, если кому-то данные хостеры не нравятся. Меня в них все устраивает.