Tons of non-NPS public land which will still be accessible. Escalante comes first to mind, but I'm not sure if Hole-in-the-rock road has been opened back up after the recent flood damage. In any case, you can access the Gulch and Boulder Creek from paved roads, and that area is pretty cool. The Boulder Mail trail is also worth investigating.
The Robbers Roost is also very worthwhile. Navigation can be a little more demanding than in most NPS settings.
Take a look at Steve Allen's guidebooks if you can get a hold of them.