Be sure to factor in altitude when choosing locations. When coming from back east some folks are not conscious of the effects on temperatures altitude plays, not to mention the effects on some folks bodies. There are places like Bryce (8000 ft.) that are high up and can be very cold in April. I have a real problem with altitude and need to acclimatize over a few nights or I suffer bad headaches. Your body may be fine with it. Just be sure to drink copious amounts of water when in the west.
I would not consider visiting canyon country complete without seeing Canyonlands Nat'l Park near Moab. Visit the "Island in the Sky" section, which is accessed off the same road to Moab as Arches. There are many locations that would provide stunning vistas for nightscapes. Mesa Arch is one that should not be missed. A five minute hike from the parking lot. It would provide a sensational shot looking east.
There is rarely anyone camping that time of year (no water) and only 12 sites at Canyonlands, but the views easily equal Grand Canyon. Only a two minute walk from the campground to the Green River Overlook. Great place for night landscapes (Bortle 2/1). There is Dead Horse State Park there with the famous "Horseshoe Bend" but not sure when they open. Before you reach the N.P there are opportunities for boondocking and there is also a BLM campground called Horsethief that is usually deserted - it would be a great spot to shoot from next to the camper..
For a Bortle 1 location stay at Goblin Valley State Park, Utah. It is nearby and on the way from Bryce to Moab.
Of course Arches N.P. is local to that same area as Canyonlands, so stay there for some incredible nightscape opportunities. It's a shame that Moab is only a few miles away from Arches, there is some light dome to factor in. At Arches my favorites are "Double Arch" and "Delicate Arch." If you want to shoot snowy mountains at night the La Sal's are nearby and spectacular. So are the Henry's. These stay snow capped all year. Remember my comment about temperatures.
Speaking of the Grand Canyon, I would suggest the North Rim. Check for weather conditions and snow. There is a wonderful observation point at the rim where Angel's Window is located that would yield countless spots for shooting nightscapes. Many opportunities to shoot without any people in the way. Be sure to watch where you step! The best part is that you will be shooting towards the south in most of them, catching the milky way prominently. Too bad Sagittarius will not be up! I like camping at the Forest Service campground near the North Entrance, good water and usually quiet. Boondocking in the area can be found easily.
If you ever decide to come farther north be sure to contact me for more astro friendly sites that are truly dark. The intersection of Idaho, Oregon and Nevada continues to be one of the darkest spots in the lower 48. The marriage of astronomy and the truck camper is a match made in heaven! I often have a few scopes in the back seat and more in my utility trailer when I set out for the last of the dark places.
Good luck with your journey!