Carrotwood Trees are common street trees in California. They are deep rooted so don't grow surface roots, evergreen and stay relatively small. The only problem in my mind is that they reseed. Keep the seeds raked up and that won't be a problem either.
