To get to the GC, get off I-40 at Williams and take AZ-64 into the park, it's just over an hour from Williams. Leave via AZ-64 to the east to US-89 and take that to Flagstaff to get back to I-40. It's about 4.5 hours from the park exit to Gallup.
If you need a place to stay for the night when you get out of the GC, when you reach US-89 go north a short distance to the Cameron Trading Post or head for Flagstaff which is an hour south. Flagstaff to Gallup is 3 hours.
