Acadia National Park in Maine. The park has 40 or so miles of carriage roads that are fun to ride. Plus, the area offers kayaking and hiking. Just be forewarned that it will be crowded.

I've been to Moab in April during a warm spell (low 90s). Low humidity only gets you so far when the temps are that high.