If you aren’t backpacking and really need to stay close to 89 you might consider staying overnight in Page. You can walk and drop down off the mesa and just go. There is a lot of National Park land. Get a good map of the area, National Geographic makes some of the area and USGS of course covers in detail. The terrain is very nice so get into it and explore. One I walked from the Marriott, where we were staying overnight during a mapping mission, to Horseshoe Bend and back. Other times I just went in nearly every direction you can imagine. I found some incredible sights.
If you are willing to drive to Escalante, UT down Hole in the Rock road are many side canyons that hold treasures. There is a BLM ranger station west of town with free permits and advice. There are outfitters closer into town that can give you good advice and can help with road conditions  The Golden Cathedral is amazing and Coyote Gulch which is longer has arches and bridges. It is very hard to go wrong but do have a good map and pay attention to navigation. We came across a young couple with brand new gear who were completely lost. I gave them advice to stay right to the left of the drainage, follow it down, look hard for a descending trail into the canyon proper and then gave the poor souls my detailed map. So again know how to navigate because straight lines don’t always work in canyon country. GPS can’t always show one the way.
We have done countless off trail, cross country hikes and found amazing things. Some places in Page will take folks to interesting places like Antelope canyon and they get the permits. Don’t wander onto the Rez without permission. Something like 70% of Utah is public lands so know where you are going and just go. Don’t slide down anything you can’t climb back up. Be mindful. Girlfriend and I have about 500 bag nights in southern Utah and always have a rollicking time.
.
