I found that calling ahead to guest houses I found in a Lonely Planet, while in India worked out great. I called ahead to them and got a room reserved. Towards the end of my trip, I was able to bear rooms without A/C, but at the beginning of the trip, A/C will be crucial. It'll help you sleep, which will help relieve jet lag.