There's SO MUCH to see in any part of Utah, your dog doesn't care if it's in a national park to enjoy it. with the various animal and vegetation dangers, Utah is not what i'd consider an off-leash State. Protect your animal and yourself, always use a leash.
Just pull off one of the many many trails that lead off into the desert from the highway (don't use the interstate at all imho) and exercise the dogs if they're high energy. then give them some water, turn on the radio, park it and check out the national park if so inclined.
my dog was plain happy to walk the road on a leash in the campground, and say high to everyone that came out to greet him. then he'd sleep in the back seat of the truck for hours, while I went to someplace not dog friendly.
