National Parks are pretty restrictive when it comes to dogs. They can be in campgrounds, and paved areas, but not on trails. If they (and you) need more walks, look into spending time in the National Forests surrounding the Parks.
For example, in the Bryce area, there is a good NF visitor center on UT12 just to the west of the park. There are some hikes into the rock formations above the center.
In the Canyonlands area, Deadhorse Pt State Park allows dogs on trails, and has canyon views that rival those in the Island Nat Park area.
