Hi Ben, I've recently booked a trip to Maui for October and spent some time to check various options for car rentals and accommodation..I've ended up booking my flight and car as a package thru Hawaiian Airlines and my accommodation from AirBnB.
So here is my advice based on my recent but single experience:
1- Accommodation, check AirBnB and www.vrbo.com, they have a fair range of options...have a look at wotif.com as well.
2- Car... I booked a mid-size SUV (Toyota RAV4 or similar) from Dollars as a flight+car package thru Hawaiian Airlines that is around US$120 per week but that is in October..if I didn't have a good package I would have booked from kimosrentacar.com or www.mauivans.com which were recommended by some people on various forums in the past...I've also been warned about the queues at the airport for collecting rental cars from mainstream agencies (thanks for the advice Yuppy).
Also, have a look at this thread:
www.seabreeze.com.au/forums/Windsurfing/General/MAUI-best-place-to-stay/