Übernachten kannst Du in z.B. Kayenta (allerdings nicht gerade billig da wenig Auswahl) oder vorher in Bluff. In Mexican Hat gibt's auch ein paar Motels - der Ort ist allerdings nicht besonders anheimelnd und die Motels sind entsprechend alt und abgewohnt.
Allerdings würde ich von Moab bis Page durchfahren, was IMO locker an einem Tag machbar ist - allerdings ohne Natural Bridges (das man sich schenken kann wenn man vorher im Arches war) aber mit Goosnecks und der Staubpiste im Monument Valley.
Den gewonnenen Tag kann man sehr gut in Page verbringen (Antelope Canyon, Horshoe Bend, weitere Slot Canyon's, Hoodoos usw.....)
Als Stop auf der Strecke Williams - L.A. würde ich wie Wolfgang den Joshua Tree empfehlen (Ü in Yucca Valley oder 29 Palms) - der Nordteil des Parks mit der Möglichkeit zu vielen kleinen Wanderungen (Barker Dam, Hidden Valley, Arch Rock, Indian Gardens, Cap Rock, Skull Rock....) mit je rund bis zu einer Stunde, bietet sich gerade im Herbst an, wenn's nicht so heiß ist.
Super ist auch der Key's View (toller Ausichtspunkt über die Wüste) und der Sonnenuntergang mit den Joshua's als Motiven.