Liquidambar styraciflua brings kaleidoscopic fall color to southern California. If it has any bearing on your interpretation USDA zones are based on average annual lows, not the coldest it gets. People constantly misinterpret this, say their zone is lower or a plant is hardier to a lower zone because they think the lowest temperature involved indicates the zone. I've never had a zip code based zone finder put me in the right zone, and when I was on the Proven Winners web site recently it had an automatic feature that read my computer and put me in the wrong zone also.

I am reluctant to plant Liquidambar styraciflua since 95% of the trees where I live are evergreen or semi-evergreen, without the reputed fall colors. One, however, in a neighbor's yard, turns a brilliant red and orange and completely sheds its leaves. I have tried to root cuttings taken from this tree, but, so far, without success. Do you have other options?

Maybe Crape Myrtles--? Their foliage is unbelievable in the autumn!

Cedar Elm is native in Texas all the way to the Rio Grande. It has a fairly muted fall color of an orangish-gold. Some years it borders on being brilliant. It is a drought resistant tree that can take extra moisture.
Prairie Flameleaf Sumac has a very dependable brilliant red color. This tree is biggest of the sumacs reaching up to 25'.
It may tend to colonize. Very drought resistant.
Bald Cypress here has a reliable rusty red color. The central Texas Hill-Country strain are knee-less.

How about Mexican sugar maple? Acer skutchii. It is native to Guadalajara and does great in Florida, with yellow fall color. Also, red maple from the southern edge of its range (Florida for example) would be good - the colors can be good all the way to the Everglades in some years! Don't forget about your native cottonwoods - Populus mexicana is cultivated as street trees a lot around Mexico City and should have good fall color. Ginkgo is worth a try there too. I have seen good fall colors on some oaks too - there are plenty in Mexico, but I would look for some in the red oak group. Shumard oak colors up well here some years/

Thank you for your answers everybody! crapemyrtles can have beautiful autumn foliage, and they're very common here so i'll definitely consider them as an option. Oh, and the flowers are a big plus!

Cedar elms are pretty trees. I've seen them many, many times when traveling in Texas. However, I have read that on the southern part of their range, they tend to be evergreen, so I don't think they'll be an option. The bald cypress and the Sumac sound good to me, though!

Mexican sugar maple isn't really native to Guadalajara, but rather to the higher mountains of Jalisco, my state. They're about a 5-hour drive from where I live and I think I'll go there next september. They're a really good option for my area, so thanks! I already have 2 ginkgo seedlings, since they seem to do rather well here. They DO have beautiful fall color, even in my warm city. Populus mexicana is a very sickly tree, even if they sometimes have a pleasant fall color (they also tend to be semi-evergeen here, ugh). I also like the red oak and [southern] red maple options. Do you know any good southern cultivars of acer rubrum?

How about bradford pears? I've read they have great fall color too. Though I'm worried they'll develop a semi-evergreen habit here.

Bradford pears have very good fall color. They tend to have weak branch structure and are not considered good choices for long term. Chanticleer and Aristocrat cultivars may be better selections for structure. Don't know how they will do in Z9-10. In addition they have excellent flower displays in spring.

There is a Big Tooth Maple that grows wild in certain parts of Texas, but its color is excellent some years and just so-so others. Assume it would be more so-so at best further south.

White oak has good red color, but requires an acidic soil. Have not seen it growing further south than edge of Z8 to upper edge of Z9.

Redbud has yellow fall color and pinkish-purple flowers in the spring. Both the Texas and Mexican Redbud varieties should do well there. They are both drought and heat resistant. I have never paid attention to the fall colors of them, so you may want to research them some more. I am raising some from seed, but for the spring-time flowers rather than the fall color.

Might let us know if you find something else.

I'm thinking that a flowering dogwood (Cornus florida) might do well here since they're hardy to zone 9. They have fantastic flowers in spring and great fall color (at least in colder climates). I already know they can grow in Mexico since my grandmother brought one seedling from the US and it did very well in Valle de Bravo (Central Mexico, slightly colder climate than mine). What do you think?

I'm also considering Chinese pistachio tree (Pistacia chinensis) since they're known to have red-orange fall color and they're hardy to zone 10b.

The best autumn colour in our summer rainfall, on the dry side, zone 11 garden came from the trident maples (acer buergerianum). The liquidambars and silky oaks (grevillea robusta) also showed up to autumn with some colour. We had a pride of India (Lagerstroemia speciosa), but it's evergreen and didn't ever colour up.

As a kid, I loved the gentle yellow autumn leaves we got from the white stinkwood (celtis africana) that shaded our north east side (important in the southern hemisphere). And that had the advantage of being indigenous for us in South Africa.

But of course, none of those are native for you.