Ich war vor ein paar Monaten dort, allerdings mit dem Rad. Kann daher zur Routensuche wenig beitragen, aber:
Die NPs sind gut besucht und auf den zahlreichen Campsites wirst du glaube ich keine Probleme haben wenn du ein bisschen rumfragst, die Amerikaner sind meistens sehr aufgeschlossen und hilfbereit (und haben häufig mehr Zeug dabei als ich besitze ). Was ich dort oft gesehen habe sind große Wasserkanister die an den Trailausgängen standen. In der Regel auch nicht markiert oder versteckt, vielleicht lassen das Leute auch zurück wenn sie zu viel haben?
Ansonsten sind die dirt roads die ich dort gefahren bin auch nicht so übel gewesen dass man unbedingt 4WD bräuchte aber das kann sich jahreszeitlich auch ändern.
Die ganzen Wüsten im Südwesten sind zwar sandig aber meistens auch steinig, Nagelartige Heringe sind meiner Meinung nach der way to go. Hatte meine leichten Heringe mit, der Großteil war verbogen nach der Tour.. Glaube Sandteile hätte ich nirgendwo gebrauchen können.