Back to you, Tobias - -
June is not a bad time to start such a trip - but you must remember that you are talking about riding between two extreme ecoregions - the Mojave Desert with June highs above 40 C to the Colorado Alpine with June lows below 0 C. Thus, it is important to plan accordingly.
If you were to do this trip in June, I would fly into Las Vegas and take the shuttle to St. George, Utah - about an hour away. (9 or 10 trips per day) Bicycling into or out of Vegas is tough. Vegas lives for the automobile. Lots of fast traffic - plus you have to get on the interstate or other dangerous autobahn no matter which way you attempt to ride out. St. George is very bike friendly with bike shops, cafes, motels. A great place to make the transition from international flight to bicycle.
From St. George you could ride to Zion NP, then loop back via Hurricane and Colorado City to Fredonia and to the North Rim of Grand Canyon NP. The North Rim has only 10% of the visitors plus has hiker/biker campsites right on the edge. You would need to backtrack via Fredonia and Kanab to hit the Utah parks - unless you were willing to do dirt. From Kanab, head north on US 89 to Bryce Canyon NP.
From Byrce, follow Hwy 12 to Capitol Reef, Hwy 24 to Hanksville, and Hwy 95 to Blanding. (This section is part of the Adventure Cycling, Western Express Route with detailed maps) From Blanding you can either stay on the Western Express route to Dolores, or head south Via US 191 and Hwy 262 to Hovenweep NM and take the paved county road from Aneth to Cortez, Colorado. Mesa Verde NP, near Cortez, has the finest Ancient Puebloan ruins in the Southwest. Hovenweep has smaller ruins that will have far fewer tourists - but you should visit Mesa Verde if you are in the area. But - - the park is not bike friendly. It's a big climb, narrow, and rangers sometimes tell cyclists to get off the road. But if you get to the park super early - there is less traffic and it is the best time for the tours of the ruins.
http://www.nps.gov/meve/planyourvisi...nformation.htm
There are two ways to get to Montrose. First, directly over Lizardhead Pass via Tulluride - the Western Express route. Second, via Durango and Silverton over the Molas Pass. Speaking of trains - the old, historic Durango & Silverton steam train runs this scenic route. A number of years ago my friend and I were able to load out bikes (unboxed) on the baggage car and ride up. This might be an option for you, too.
From Silverton you can fly down the Million Dollar Highway to Montrose. Or you can do a little dirt over Engineer Pass to Lake City and then to Gunnison. The Western Express uses US 50 from Montrose to Gunnison - lots of ups and downs and moderate+ traffic. From Gunnison, you can continue on the Western Express to Salida or you can head up thru Almont to Cottonwood Pass Road and Buena Vista - mostly paved, some dirt, but spectacular.
If it were me, I would head north to Leadville, then continue over Fremont Pass to Frisco and Silverthorne. If you run out of time, you can awys pack your bikes at a bike shop here and shuttle to the Denver airport. But better - - continue north to Kremmling - then head east to Granby and take Trail Ridge Road over the top of the world in Rocky Mountain NP. You can end your trip in Estes Park. Box up your bikes at a bike shop there and shuttle to DIA.