I would say Burr oak. The redbud and Pistache, I don't have, but the better quality tree IMHO would be the Burr oak, or any oak, but the short lived ones like Quercus Nigra (water oak) or Quercus Laurifolia (Laurel oak) or Sawtooth oaks forget the latin for it. I have heard Pistache is invasive some places. The redbud isn't long lived but maybe you aren't worried about that anyway. My Burr oak is about 16 ft tall and is about 6-7 years old, not too slow.

contact your local COUNTY extension office.. they probably can provide local suggestions for such

ken

IMHO,
Chinese Pistache as they originate from near dessert regions are the best adapted to your conditions. As for Oaks, not any ole oak will do. Water Oak is called that for a reason, and definitely would not like your climate. Western Redbud would be better adapted than Eastern Redbud, etc.

You best bet is to do exactly what Ken said, although your local municipality might be of some help as well.

Arktrees

Concur with above and would also note that the vast majority of redbud cultivars are Cercis canadensis, the eastern redbud. There are a few C. occidentalis such as 'Alba' (white flowered) but most are just the straight species. They are way more drought-tolerant than the canadensis.

I've never seen a Chinese Pistache that looked 'good', and there's plenty of them used as street trees here. Other than the fall color (which varies), they're ugly in my opinion.

vieja,
My vote also goes for bur oak. As a species, very adaptable to a wide range of environmental conditions and soil types & pH. Certainly, if you can get one selected from local provenance (or similar ecosystem), it's likely to have fewer issues. Q.macrocarpa is long-lived and drought-resistant, once established - and in my plantings, has been among the fastest-growing of any oak, typically putting on 2+ ft of growth per year, in youth. YMMV, of course.

Red Bud is fairly drought tolerant. Tx. Red Bud even more so, but it will not likely make 35'. More like 15'.
Cedar Elm might be another choice. It should grow anywhere Pecan would grow. Has a dependable muted orange/gold fall color.
Prairie Flameleaf Sumac (rhus lanceolata) will grow 15-25', is very drought/heat resistant, and has dependable red fall color.
Good luck.

My vote goes to burr oak....very tough tree

Thank you everyone! I think we will try the Burr Oak as I believe it tends to have more of a deep tap root than many lateral/surface roots I've read (state tree of my home state of Iowa too!). The City has recently planted them now in our parks & they seem to look good & don't think those curious acorns would be too much of a mess when they fall (our pecan dropped the nuts & the darn dogs learned to chew off the husk & eat the nutmeat & leave the sharp hulls on the lawn for me to walk on (barefoot)! We have a ?50 yr. old staghorn sumac that I love the shape, medium height, fall leaf colors... but, it sends out runners underground that I have to pull up when they come up & invade the lawn, flower beds, etc. It seems to be more of a decorative tree than a shade tree too. The pistache I've seen planted here locally are still young so don't know if I'd like them as they got bigger... but the fall colors are pretty! I do see that the redbuds of the neighbor's drop seeds that seem to germinate all too well ... not a 'plus'!

So, given our altitude, cold, heat, arid climate ... I
think you've helped us make the decision ... a burr oak!

Just make sure to get one from the southern part of its range, a northern tree from Michigan may not perform well in the heat of NM.

Bur Oak is a good choice. Would imagine you will be happy with it. Mine seems to grow in spurts. It will do nothing for the longest time, then suddenly in about 2-3 weeks it will grow anywhere from 8-12". Then it will sit and nothing til it decides it wants to grow. I envision it's roots are growing during this time and when they have expanded enough, the tree decides its time to grow!

scotjute: Glad to hear you are happy with the burr oak; do the unique acorns pose a littering problem with your tree? The ones at our Park are sought after so most picked up as soon as they fall! Wonder if there are male trees that wouldn't have the acorns ... but guess then one would have the pollen?! You are in a warmer zone but in Texas so would think the conditions there would be similar to where we live. Thanks for your input!