You should be able to get reasonable rooms in either Holbrook or Winslow. I40 kinda sucks with all the truck traffic but I have a good friend that is Navajo and lives in Page and his parents live north of Gallup a little bit. He goes to Flagstaff on highway 89 and then hops on I40 rather than driving across the Rez just due to livestock on the road and drivers coming on and off the highway unexpectedly. And it has become a commute for him over the last 12 years. I also replied to your pm. Enjoy the ride, wherever you end up!