Thanks everyone for your input. I think I'll rent a car in Oahu now, probably cheaper than taking cab everywhere.

Cholula, if you can post the cab name (and maybe average price), that'd be great!