Você não precisa de muito, mas precisa de uma boa quantia. Em geral, 1 Mb / seg é suficiente para coisas de baixa qualidade.
Para os vídeos 480p Hulu e os vídeos do YouTube, você vai querer pelo menos 3 Mb / seg, e mesmo assim pode ficar um pouco instável se você não tiver uma conexão muito sólida. Para o vídeo de streaming extremo (1080i ou o que o YouTube está oferecendo agora), não acho que haja uma conexão grande o suficiente. Eu tenho conexões de alta largura de banda de 30 Mb / s e ainda recebo atrasos.
A melhor experiência que tenho é de 5 Mb / seg. Sem atrasos, sempre totalmente em buffer, e posso escolher a melhor qualidade que eu quiser.