How about cork oak? (if you're able to find it) As far as desert trees, I think you're thinking of Palo Verde. I think it would meet all your needs. If you were willing to have fruit, a fig tree could be another option, but they can get messy if you don't harvest all the fruit before it falls to the ground (unless you got a male fig tree). Pakistan mulberry might be another option, this variety is more tolerant to heat, and mulberry trees have beautiful shade leaf foliage, but again, if you don't pick all those mulberries it can be messy. Last one to mention is a "California pepper tree" (actually originates from Peru). It's a medium-fast grower and is fairly drought tolerant. But a word of caution, if you do supply it with a lot of water for many years and it does grow big, but then it goes years without any water at all, it will suffer drought stress and become susceptible to disease. Only the bush-level trees that haven't grown to a huge size are truly fully drought tolerant. They can drop a lot of leaves and little red berries, so can be a bit messy. Pepper trees also put out a lot of surface roots, so it's unlikely you're going to plant anything below it. Before you plant one, I'd rub the leaves across the top of your hand because there are a small number of people who have a contact allergy to the leaves. They can be a beautiful medium small tree.

Quercus, possibly kellogii. This post was edited by formandfoliage on Mon, Apr 21, 14 at 1:17

I will add: Camphor Tree, if you have enough space, the roots can be expansive. The leaves smell aromatic. This can be a big tree and should not be planted too close to the house or sidewalks. Pepper Tree Spanish Cork Oak, they are drought tolerant and don't get too big, and have amazing squishy bark, this is where cork stoppers on wine bottles come from. Pomegranate grows exceptionally well in this climate. Even if you don't like eating them the fruits can be very decorative hanging from the tree, and the tree also produces pretty fiery orange blossoms. Pomegranate usually grows more like a giant bush-tree though, not really the best for shade. A lot of people have never tried a truly fresh pomegranate right off the tree, they taste much much better when really fresh. And a lot of people do not know the proper technique for cutting open a pomegranate and removing the arils, so they wrongly think eating pomegranate is too much work and too messy. When it comes to Mulberry trees, Persian Black is by far the best tasting variety. However, if you're in climate zone 10 Pakistan Mulberry will grow better and is also a good tasting variety, with larger fruit size too. If you go with a fruitless male Mulberry (as some people do to avoid all the messy berries falling), there could be pollen allergy issues (if not you, someone else in the neighborhood). The Black varieties are the best tasting, but the black berries can make a mess on the ground and stain the sidewalk, or get tracked indoors on your shoes on the carpet, so that's something that should be considered. Another little fact, mulberry leaves are not poisonous and can be fed to pigs or goats, a favorite food of silkworms too. Mulberry trees have beautiful shade foliage. If you're looking for some more exotic choices you might also see this thread: Sacred trees in India

I would definitely want a closeup of the leaves in your hand before going any farther than, “it appears to be a tree.”