I rented a 172 from Maui Aviators (
http://www.mauiaviators.com/) last year and had a pretty good experience. They spent some time on the ground with me marking up a sectional chart and discussing the various VFR procedures and reporting points applicable to Maui's area. They reviewed my logbook and wanted to know how much recent time and time in type I had. Then I went up with one of their instructors for a brief checkride. We did a steep turn, some landings to demonstrate that I could handle Maui's fairly extensive cross winds, and they signed me off to rent. Their 172s are well used, but serviceable. Lots of fun flying along the cliffs of Molakai, and we saw a number of whales also. We'll probably do it again this year.
It was interesting landing at Maui. The recommended landing speed for my airplane, a Bellanca Super Viking, is 90mph; the 172's landing speed is 65mph. Combined with the fairly significant headwind, my ground speed when landing was probably about half of the Bellanca's. It felt as if I weren't even moving...