I was there in Dec and you couldn't book the low cost airlines online. Only locals could using an Indian credit card. So you have to depend on a travel agent to book for you. As long as you know the price(with tax) then you can ask what the booking fee is. It varies a lot so check a few travel agents. Also the prices change quickly so if you check one day and then go a day later it may be higher, don't assume they are trying to rip you off. That said there are lots of shady travel agents so be aware.
I used the online booking system for the train ticket and never had to stand in a line at an Indian train station the whole time I was there. If the trains are full you can use the foreigner quota as mentioned before or just get on the train and they will find you a seat-unless it is a public holiday!