Either redbud or dogwood would suit the partially shady spot. Redbud produces those seed pods -- they degrade pretty quickly but I'm not sure what your "mess" tolerance is like. You may also want to consider crabapple, some of the larger crepe myrtle varieties, and chaste tree or grancy greybeard (although it grows slowly.)

For the medium/large tree, what kind of height and width are you thinking DO you have a preferred growth habit? For example, do you want tall and narrow, or spreading, or roundish?

Thanks for your reply, alabamanicole .

The seedpods are an acceptable level of mess for us, we just don't want nuts, gumballs, or anything of that sort.

The medium/large tree we'd like to have a taller than our 2 story home but not so large as to overwhelm it ... 40-50 feet or so. For sure a shade tree and I'd love a spreading canopy whereas my husband has no preference so something. Definitely nothing columnar or weeping.

A tree that the kids could climb in when they're older would be icing on the cake though not necessary.

I'm assuming an oaks are out of the picture? You may want to look at Honeylocust, Catalpa, Lacebark Elm and Black Gum.

Honeylocust has thorns but there are thornless varieties available. (I haven't seen one yet.) And it's native.

Catalpa is an old southern favorite. It does drop seed pods but I haven't seen a mess in my neighbor's yard so I think it's probably not too bad. They attract sphinx moths if anyone in the house is a fisherman.

Black Gum does reseed itself freely, but if this is going in an area that is mowed it won't be a problem. It doesn't have the balls like sweet gum. Also native and a great shade producer.

Regarding Lacebark Elem aka Chinese Elm, you want Ulmus parvifolia, not Ulmus pumila. The true lacebark elm has lovely bark. It's not immune to the elm disease but is very resistant. Reseeds freely; can be semi-invasive. Also a good shade tree.

There are also a ton of different maples, but they tend to be intolerant of clay, compacted soils, which defines much of Alabama!

If the tree you took out was tearing up your lawn by growing roots above ground, that suggests your soil is very compacted or wet or both. If so, pretty much any tree is going to do the same -- you may want to evaluate your soil, and if it is heavy, pick something that handles heavy soil well, like the Catalpa or the Black Gum. Or it may just be a tree that's prone to growing surface roots -- what kind of tree was it?

Thank you, again, for the help!

The Catalpa is a stunning tree (based on the quick google image search I just did). I'll have to look into that one some more.

The tree we took out was a walnut. The previous home owners (we've only lived here for 2 years) didn't take care of it at all. It was planted so close to the house that you could touch it from our front porch, many limbs were broken from years of storms so it looked scraggly, and the lawn under it is completely barren due to the walnuts just sitting in the yard for who knows how many years. (Judging by the amount of fallen leaves in the back yard which also killed the lawn, I'd say many many years of yard neglect.) The new tree is not going in the same area so the poisoned soil (which we're working on rebalancing) shouldn't be an issue.

Maples have a lot of surface roots but red maples grow very well in all part of AL. I'm a big fan of magnolias (best trees to climb) but the leaf litter is a turn of to some. Maybe a sourwood or ash?

Catalpas can be host to yellow caterpillars (catalpa worms) that are very juicy and make the most awesome fish bait. However, the worms come out every so often in warm weather to feed on the leaves of the tree and may leave you with a nearly naked tree. The trees always resprout. A possible side effect is that the worms are also loved by wasps, fire ants and birds.

Not all catalpas get the worms though.

Not all people love the worms when they fall out of trees, either. As a specimen tree in a front yard, I would do it, but in the backyard with lots of outdoor activity, perhaps not.

Sourwood usually doesn't get tall enough. Ash would work, but they tend to be short-lived trees (~50 years). Hackberries always get aphids and drip stocky goo everywhere. Every tree has it's ups and downs!

If you decide on a maple, don't go with a sugar maple, They don't do well over the long haul in our heat and humidity. If you want an evergreen, you might consider a wax myrtle or a holly. Either of those can be limbed up or left as spreading, ground-hugging trees. Like jcalhoun , I love magnolias for medium- large, great climbing trees. I have liriope growing under mine and just leave the leaves where they fall. They're not bad about blowing around the neighborhood like sycamore leaves. Any that fall beyond the liriope, l blow or rake to use as mulch. The leaves and seed pods break down more quickly than you might think and make great mulch around shrubs.