Big Bend and then north towards Alamogordo and White sands is very doable. From there head north to I-40 and head towards Flagstaff or head down to I-20 and head towards some of my favorite places for dispersed camping. Between Lordsburg, NM and the AZ border NM SR 80 heads south first in NM and then crosses into AZ and eventually brings you to the Mexico border near Douglas, Az. Just before Douglas, continue on SR 80 west to Bisbee, Tombstone areas and then out to Yuma. The areas around Bisbee to Tombstone are gorgeous, 6-7,000' elevation and lots of lonely trails N/NW of town. Heading further west you could do El Camino Del Diablo which is amazing. It begins in Yuma and ends in Ajo, AZ.
Two things about El Camino. It is nearly impassable for days if it has rained. I am certain they just got rain/snow there with this last system. If the sun comes out and humidity drops, the muddy areas dry out within days. You have to apply for a permit . You have to register before since it goes through several military areas - Luke AFB, Goldwater bombing range, etc.
You will also pass through two Border Patrol forward bases. It is safe and awesome out there. Several YouTube videos online so you can get an idea of what it looks like.