Stefan -
I've lived mostly in Wyoming since 1990 and taught in Montana.
My sister lives in New Mexico - so I know the Four Corners regions pretty well too.
I tend to recommend caution with the weather because it is so highly variable.
People who have only taken a trip or two out West may have been lucky.
Especialy in the spring or fall when things can change in a matter of hours.
I noticed that you mentioned whether or not you should have a mountain bike.
If you plan on doing a lot of dirt roads - you should.
You heard about the flooding in Yellowstone.
Floods like that are not uncommon in the Intermountain West.
Arid regions with 10 inches of average rainfall don't get 8 inches one year and 12 the next.
They might get 2 years with 10 inches; 6 with 3-5 inches; 1 with 20; and one with 36.
What that means is that remote dirt roads that are o.k. one year may be horrible the next.
They are rarely maintained and can have deep washouts.
I have had two crashes where I came over a little rise and there was a huge gully.
And I was on a mountain bike both times.
Plus, it's not like the Balkans - because you may be 150+ km from any water or assistance.
Some shorter dirt segments are o.k. - provided you touch base with others here.
AND you inquire on your ride with reliable sources before you head out.
Southern Utah - Be aware that bicycles are not allowed through the Zion N.P. tunnel.
I have bothered ZNP for years about the hardship this places upon cyclists.
Bicycles haven't gotten bigger over the years - it's the huge RVs.
There is one-way traffic with a flagger most of the year.
Sometimes the flagger will try to help you get a truck for your bike.
Other times you have to beg for yourself.
(This is especially dangerous for women cyclists.)
Also, Zion has no hiker/biker campsites.
You need to reserve a campsite well in advance.
Yes, that is difficult to do 3 weeks into your tour -
but you have to make your best guess and do it early.
I'll write Zion yet again asking for them to improve cyclist access.
If you cannot find camping in the park and stealth camp,
you can be arrested - esp. if you are in the park - and face a large fine.
Camping can also be a challenge at Bryce and Capitol Reef.
But Zion is the worst with the highest visitation levels.
Both Bryce and Capitol have public lands just ourside the parks.
Or - - - you can plan a short day into the park,
so that you arrive at the campground aby noon.
Utah Hwy 95 is verrrryy remote.
And the Hite Crossing store/marina has been iffy over the years.
Part of the reason is because reservoir water levels are at record lows.
If boats can't access the lake, then the marina closes.
If the store/marina is closed it is 150 km from Hanksville to Natural Bridge.
https://www.nps.gov/glca/planyourvisit/hite.htmYou will probably want to head into Blanding to resupply.
And wash the red dust off.
Best - Juan