Depends on your budget.
I would say that colo is the best, but you also need to be hosted on a high quality network if you want the best performance.
Long-term, colo is the way to go. There is a bit less convenience with colo, though.
If I was doing the same, I would probably run a colo for the site itself but integrate with a CDN for all the actual videos. Akamai & Limelight would be great for this, but on the expensive side. Other CDNs still provide valuable benefits over running the videos from a single server, though.