With the potential contrast involved, Velvia would be problematic. I never found much use for it in the desert, even back when it was still relatively affordable in 8x10 sheets. A polarizer would even make it worse in terms of rendering earthtones realistically. I don't like the way they tend to kill the magic of natural glare and sparkle anyway unless one is thoughtful. Rock sheen and "desert varnish" is one of great beauties of our desert landscapes; but it depends on the specific geology.
ND grads seem to take a lot of experience to get right; in my hundreds of trips, I've never used one, and probably never will. It's really easy to make a scene look fake that way unless you've learned nuance first.
If the lighting ratio is just too much, sometimes you simply have to sacrifice the shadows and let them go black. Ektar will give you about a stop more realistic wiggle room either side than a typical slide film; about a stop and a half more either side than Velvia.
And it depends what you want out of it, and how you intend to print it, if at all. In recent years I've had great results with Ektar CN film and earthtones, but it's contingent on two things : 1) meter just as carefully as you would with a slide film (don't bet on "latitude"); 2) you have to color temp balance it with appropriate warming filters if bluish overcast or deep blue shadows are encountered. The latter is likely to be abundant in Big Bend (don't count on any of that "I can fix anything in PS afterwards; you can't).
I always carry a 1B light pink skylight filter and KR1.5 or 81B warming filter on such trips. Ektar isn't artificially "fleshtone" warmed like most color neg flms; but it is a lot better overall hue balanced and saturated. Blue skies tend to come out a little cyan inflected unless you counter that with a 1B filter.
Portra 160 would be rather bland to my taste for those kind of scenes, but it's more forgiving.