Gallup NM is an old tourist stop on 66, lots of indian crafts.
Just into AZ is the Petrified National Forest park which you can loop down through and circle back to Holbrook AZ. Further west is Homolove State Park, fairly new, good ancient indian ruins.
Further west, past Meteor Crater, just before you get to Flagstaff, is Walnut Canyon park with a nice walking tour of cave dwellings.
After Flagstaff and the Grand Canyon, is Seligman, AZ where you can get off the interstate and take old 66 as far as Kingman AZ. The last "town" on that route is Hackberry. Be sure you stop awhile there. It's only a store, but it's full of old 66 memorabilia.
