All the usual hire companies are in Cairns (Avis, budget, hertz, europcar, redspot) and have new cars. Cars hired from the airport have a daily surcharge added to the bill, so you can save some money if you pick up and return one in the city. It's a $20 taxi ride or less in a shuttle bus to the CBD.

Good luck and enjoy your holiday. !