Sevenload seems to be one of the best hosts. They barely compress the video they host and it is excellent quality.

Problem is, the thumbnails. They are active GIF animations. When you add them to your site they automatically start and don't stop. Anybody know how to stop the animation without having to host the gifs somewhere else.