21 days is a nice window. Last year I only went as far as Williams, Arizona, but my route out and back to that point was pretty similar to yours. I'm going back to Colorado/New Mexico the end of June, but this time I'm doing a lot less interstate. I'm going cross most of Missouri and Kansas on US-36 going out, coming back I'm keeping a little further south and spending some time in Arkansas before coming back. If you're not heading out until later in the summer, you can check the forum, I'll post a comparison, re time, scenery, riding experience.
As for cops, camping and motels - you can find pretty cheap camping in the U.S. - alot of the State parks run $15/18 - I camped in a municipal campground in Gothenburg, Nebraska for $10.00 and that included a shower (lukewarm trickle - but ya know- 10 bucks).
Cops - as far as I can tell, non-existent in Colorado and Utah - but running down 89 from Utah into Arizona, I saw three within the first hour of hitting the state line - probably wouldn't have noticed if they hadn't been so noticably absent until that point.
Highlights for me in Arizona were my 89A run through Oak Creek Canyon, Sedona and to Jerome - ghost town on the side of the mountain, and a little sidetrip to Petrified Forest National Park - $5.00 to get in and really unique scenery of the Painted Desert. Utah - from the moment I rode in to the moment I rode out - loved it. Arches, Bryce Canyon, Scenic Route 128. Colorado - highlight last year was the Peak-to-Peak Highway to Estes, then Trail Ridge Road through the Rockies - I didn't do the Million Dollar Highway last year, but this year I'm camping there for 2 days.
Wheelie Boy has done a route similar to yours and posted a interesting ride report you might find helpful.