Search for a host offering ffmpeg/ffmpeg-php since that's a requirements for most of those Youtube clone.
And if you're just starting, do yourself a favor, and go for a host offering reasonable packages, and not with those offering the world for $3.
I would recommend a VPS and later getting a dedicated. Most shared host will suspend you for high CPU usage.
I would suggest the same. You'll likely be hard pressed to find a reliable host with the capacity necessary for such a site in a shared hosting environment. Even if you do find one, at some point even they will suggest you make a move to a dedicated solution.