Hello,
I would say BSNL offers the best speed now a days but there customer service is hell. somewhat ok with the connection reliabilty.
The reason why customer said there broadband connection is very slow because there should be only 6 kms from the premises to the exchange as of DSL Technology.
My house is very near to the exchange and I am getting the speed of 600kbps as download and 250 kbps as upload. Check your speed with http://www.speakeasy.net/speedtest.
If your are not getting the speed then I would suggest the best way to fix it.
Never go with Airtel. They sucks our money anything. Stick with BSNL because it's worth for money what we paid.
Suresh