You might consider the Japanese Raisin Tree
http://www.ces.ncsu.edu/depts/hort/consumer/factsheets/trees-new/hovenia_dulcis.html

http://www.crfg.org/pubs/ff/raisintree.html
The raisin tree is deciduous and can grow to a height of 70 feet or more, but cultivated specimens typically reach a height of about 30 feet with a singular trunk and a rounded head. The lower branches frequently drop off leaving a fairly high crotch. Growth rate is moderate, perhaps a foot or two per year, more when young and less when old. Raisin trees are particularly handsome when planted in groups. The deeply fissured bark is counterpointed by gently undulating branches and overlapping leaves

The edible "raisins" are not a fruit at all but a short, swollen mature flower stalk or peduncle which supports the inedible seed pod. As the pod matures, the peduncle of stem attaching it to the cluster swells, becomes knobby and turns a translucent reddish brown. A pear-like flavor develops as the sugars increase, and the peduncle is ready to eat when it falls to the ground. Although the edible portions are small, close to the size of a raisin, the crop is copious.

Here is a link that might be useful: Japanese Raisin Tree

Taxodium mucronatum or Acer truncatum. There are some great truncatum maple cultivars being produced in Texas and slowly making their way to online nurseries. One such nursery is Sooner Plant Farm. The cultivar 'Fire Dragon' is very popular.

Dax

You are going to have trouble achieving a large quality shade tree on your soil conditions. Medium size :30-40' is about the best you can hope for. Growth after 25' will probably be slow.
Cedar Elm is probably the best choice for both size and color in a quality tree.
Pecan and Bur Oak are even better for size and shade. Pecan has yellow fall color that is very short-lived. Bur Oak has brown. Pecan can achieve 3' per yr; Bur Oak about 2'. Both of these are dependant on good soil conditions which you don't have. Both make fine shade trees and are drought-tolerant once established. Choose native pecan in lieu of grafted for best growth and form, as many grafted pecans are selected for nut production, not optimum tree growth. My yard Bur Oak is now achieving 18-24"/yr growth @ 8' hgt. in soil about 6" deeper than yrs. It was started as an acorn. Another by creek bottom hit 3' last yr.
Some Conifers you might consider would be Eastern Red Cedar and Arizona Cypress (Carolina Sapphire). These are quality reliable conifers that will grow at 2' or so per yr. Arizona Cypress will be more drought tolerant and has blue color.
Big Tooth Maple is beautiful but can be finicky. Would not use where I want reliable shade quickly.
Have heard good things about Mexican Sycamore.

Since you want to be a little different, check into either a Chinkapin oak(Q. muhlenbergii) or Sierra Red oak (Q. canbyi). Both grow on limestone and do well there. I think Fanicks has some Sierra red oaks.

Lacebark elm can give you some shade pretty quickly before others do.

Taxodium mucronatum (Montezuma cypress aka Mexican Bald cypress). They can grow pretty tall and stay green into late fall/early winter before turning color in the middle of the winter then start growing before others do. Very short dormant winter compared to Bald Cypress. That's what I planted in the south side of the house. One already grew 3 feet in its first year with plenty of growing season left. It's supposed to grow 3-5 feet a year for first 5-10 years before slowing down depending on how much rainfall or supplemental watering they get,

blakrab: Thanks for the tip on the Japanese Raisin Tree. That does look intriguing! From checking on a couple of websites, it appears to be drought tolerant and somewhat tolerant of alkalinity although it looks like it may stay a little smaller than I'd prefer. I lived in Japan for a number of years and didn't notice this one. I'll check into it further.

gardener365: Thanks for the tips on the Montezuma Cypress and the Shantung Maple. I had been considering the Shantung "Fire Dragon" but wasn't sure if it might stay pretty small. If anyone has gotten some good growth out of these down here in the Austin/San Antonio area, I'd love to hear their successes. Aesthetically, I am not as crazy about the cypress as a tree for the yard, although I like them near water.

scotjute: Yes, I am sure you are right that the soil conditions I have will limit the ultimate height of any tree that I plant. I hope to compensate as much as I can early on by top-dressing with compost the first few years. However the reality of a tree trying to grow into that limestone base underneath will kick in. That is a great idea about getting a native Pecan. I wonder if nurseries carry them? I haven't done a lot of searching yet, but they do all seem to be focused on carrying grafted varieties that are good at producing nice nuts. In my case, I really just like the look of a Pecan tree and don't really care what it produces just that it grow vigorously. Do you have any ideas where I can find a decent sized native Pecan down here? Burr Oaks sure do sound like nice trees but I am wanting to steer away from another Oak as I already have a Red Oak and several Live Oaks. It's too bad about those Bigtooth Maples being so finicky, I guess I don't really want to roll the dice and have one not do well. I am not as keen on the cedars although if I was going to get one, I suppose a nice stately Deodar would look good. There is a large grove of 15-20' tall Blue Atlas Cedars planted at the Bass Pro shop on I-10 just NW of San Antonio that look less than totally happy. I am guessing it is just too hot here in the summer for them to do well. Too bad though, since I love to plant one of them!

dricha: I have seen Chinkapin Oaks and do like them too, I had not heard of Sierra Red Oak. Does it look or have growth habits that are greatly different than the standard Red Oak? Thanks for the heads up on Fanicks, they seem to be highly regarded. I'll head out there and have a look.

lou_midlothian_tx : Thanks for the info on the cypress, they do seem to grow pretty rapidly. I've read some of your posts on growing Shantung and Bigtooth Maples. Your soil at your previous local looked pretty tough from your photos too. What are your thoughts on the ultimate size on the Shantung? I know your posts indicated that your trees were doing well, what sort of growth rates did you get?
Mexican Sycamore and a native Pecan still look like pretty good bets for me based on what I am hearing and my preferences. You all please let me know if you have any other suggestions. Thanks!

I just posted a ID THAT TREE type thread... we have a tree that is growing VERY fast. If I find out what it is, I'll let you know. We're in Dallas TX. Photo of it at 3 yrs. BTW, I'm pretty sure it's NOT a Bradford Pear.. it's leaves are 6+inches in length.

For what you are wanting, I would contact Womack Nursery and tell them what you are looking for and see what they recommend. May want to special order a tree. Some of their grafted pecans may be good shade trees and I think they have wild pecan seedlings available, not sure about the sizes. They ship out typically from December to March. Last year there was a run on pecan trees and they were sold out by first of January, so I would call them early to reserve a tree.
http://www.womacknursery.com/pecanSeedlings.html

The ultimate size for shantung maple? Who knows? It's sorta like Japanese maples that come with all kinds of size and form. Some seem to grow pretty fast in the first few years depending on the weather. My very first 'Fire Dragon' planted in the spring of 2006 is over 20 feet tall and maybe 15' wide from what I can tell when I drove by the other day. I contacted someone who had grown SMs before and he said he had SMs over 40 ft tall! If the weather is right (mild temperature and enough rain), I'd see 4-5 feet of growth on young SM trees. That's what I am seeing on mine and others this year. I'm actually jealous of the new homeowner. Just a few more years and he will have magnificent fall colors from 8 shantung maples... Dax listed one place to get Fire Dragon. MrMaples website has Blaine's, Skinny Dragon and Golden Dragon. You can always drive to Metro Maples in Ft Worth to get any one of these cultivars in the fall. Metro Maples can't keep up with the demands for them. Already sold out till fall. I'd say get Super Dragon but I have no idea when it will be available. It's such a cool tree with lime green color leaves with white veins.

Here is a link that might be useful: Metro Maples