What is the required upload speed I need to stream HD video on web? Curently I am in process of talking to various ISPs so I can find the best solution, but seems like they can't help me since a lot of them are offering low upload speed connections.
It depends on a lot of details you haven't covered here. You need about 3 Mbps to have sufficient overhead to maintain a well compressed 720p stream (the quality that Hulu Plus uses), but you would need specialized hardware to keep a good quality 720p stream encoding on the fly. Most likely, you are going to be looking at significantly more than that if you are trying to software or CUDA encode on the fly since it won't be able to get as high of quality with as little data.
Note that this is only talking about sending the feed to a single system as well. The most common case for distributing to multiple viewers is to encode and upload to either a CDN (content distribution network) or your own live streaming server that is in a data center somewhere. With that kind of a setup, your one connection can be replicated out over a 100Mbps or 1000Mbps connection to many more viewers.
You can use overly compressed settings to reduce the bandwidth needs further, but it will start showing as a really noticeable reduction in meaningful resolution. There might still be an HD number of pixels, but they won't have the kind of detail you'd normally expect from HD since it would be over-compressed.
There can be a lot of variation on that too though. If you are live-streaming something that isn't real life, compression tricks can be used to make it much more highly compressed for example, so this still isn't a one size fits all answer, but it covers the general live video streaming case for professional level quality.