I've used Vodafone and have been satisfied with their service (Bangalore, Mumbai, New Delhi, Jaipur and other parts of Rajasthan, Ahmedabad, Mysore, some rural parts of Karnataka...). No personal experience with Agra or Varanasi, I'm afraid.

I'll add that the only operator about whom I have heard negative comments is BSNL - they appear not to be at all competitive in their pricing, and there are reports that roaming within India is sometimes problematic with them.