Location, location, location. This is my first time to Maui and driving is a must. Getting to Haeakala took about 40 minutes. Getting to the beginning of Hana road is about 40 minutes. I don't think you can avoid that, unless you get a place to stay near there since most of the resorts/condos are located on the west coast. As a pleasant surprise, Lehaina is a nice little town and we walked around it every night.