My vote is for the 'Teddy bear' Magnolia. It is evergreen and stays relatively small. Only problem will be timing the planting and dealing with the water bans until it is established.

I agree totally that a Norwegian Acer is out of the question!

If you want to go with deciduous though the Trident is going to be the best. Character and smaller leaves.

Another definite no is going to be a 'Red Sunset' with the graft rejection issues.

Maybe one of the columnare red maples. Not sure how tall they gert, but they would fit with the sugar maple otherwise, and certainly be able to handle your climate and soil. Don't give up on saving the others. Also various asian maple might be a possibility. They are rarer, but can be found. I ran across two 2.5" caliper Mancharian maples locally this spring. VERY rare, yet here they are. Now if I only had a place for them......

Red Maple Possibilities:
Acer rubrum 'Armstrong'
Acer rubrum 'Bowhall'
Acer rubrum 'Red Rocket'
Acer rubrum 'Red Super Sonic'
Acer rubrum 'Somerset'

Asian Maples:
Acer triflorum
Acer truncatum
many others in this size range that are fairly resilient

Here is a link that might be useful: Sooner Plant Farm

Forgot to add:

Chinese Pistache
We LOVE ours.

Acer truncatum hybrids:
Pacific Sunset Maple
Norwegian Sunset Maple
You should be able to find these. The local botanical garden has them in the parking lot, and they have to be one of the most impressively vigorous trees I have ever seen, and they suffered NO apparent damage in the worst ice storm on record this past winter. They are not small trees. Can't tell you only color, as they have only been there two growing season, and are not showing their true selves. But the pictures look nice anyway.

Acer truncatum (shantung maple) is pretty nice. It doesn't get too large but mine went from puny stick 5ft in 2006 to 13,14 feet now. It's called 'Fire Dragon' known for its red fall color (bright yellow is typical fall color). you probably would have to drive all the way to Ft Worth, Texas for that unfortunately. Click on the picture to look at album on the progress of 'Fire Dragon' since spring of 2006.
{{gwi:355788}}From Fire Dragon

Thanks for the suggestions.

I have been looking for several years for bowhalls or similar columnar red maple and have not been able to find any around here which is strange because you'd think a tree that doesn't interfere with powerlines and is fine for narrower planting situations that trees like this would be more popular.

That dying apollo is not between the houses like the others so there is a little more room but definitely not room for a wide spreading tree like chinese pistache.

The acer truncatum looks like it has everything going for it except a big question mark on the spread.
Lou, I tried to see the progress by clicking on the photo but didn't see any other way to proceed once I did. I'm curious to know more about that tree.

I wasn't planning on replacing the others. I haven't given up on those.

And I was planning on doing the replacement in the fall anyway so I've got the whole summer to figure this out.

We have a Fire Dragon that the owner of Metro Maples (and patent holder) brought to us about 18 months ago, when he happening to be coming to the area. It has done very well. It has endured several late freezes in the 21-25F temp range, after buds have opened, and shots about 6 inches long, with very little to no damage resulting. Tough little tree. I can look out the window at ours as I type and see a very dark green dense body to the tree, with red growing points at the end of the shots. Hasn't got the glossy leaves that it does when it gets hot yet. We are very happy with ours. Look to the link provided for additional info. And since you seem to go for the rarer stuff, it would be a candidate from that standpoint as well. I think he will ship smaller ones during winter, or I think he did at one time anyway.

Also on the Pistache, I can speak for elsewhere, but those that are planted here are kinda like a lollipop in from. They are not that greatly spreading, but maybe that just because of the age of the trees. These are fairly new to the area, and mostly planted near roadways, and parking lots with something like 8-10" caliper. Occasionally elsewhere. But these aren't as large.

As for the other columnar trees, you will probable have to special order them. I don't know this, but I would expect that most of these are expected to be sold to towns, cites, and landscapers for commercial projects. You might try a landscaper in the area as well. Try the local cities, and see what they will tell you. Might even piggyback one on for you in their next shipment. Just depends. Also look to tree farms within driving distance. There are a goodly number in that area of the world. Sometimes they can be of help. Nurseries will have you believe they are the only place to get the plants you want, but that's not always the case.

Arktrees

Here is a link that might be useful: Metro Maples

You are right. We don't really know what 'Fire Dragon' will really turn out to be. So far, I have 3 different shantung maples and they all have very different growing habits so I'm afraid I can't help you there but it's a nice tree.

I was about to suggest you to try Rocket Maple from Oikos Tree Crop but they don't have that shantung maple hybrid anymore. It's supposed to grow tall and narrow (8 ft wide). It seems that you have to go out of the way to find something that will grow narrow.

How about Shawnee Brave bald cypress?

I hope this works better....
{{gwi:345677}}Fire Dragon

Wow that's incredible.

Look what I found.
Karpick red maple
{{gwi:355791}}

I think the problem with this cultivar is the mature spread is just too big and the surface roots are going to destroy the edging in no time and might even adversely effect the surrounding shrubs. (va. sweetspire)
But the above photo is the narrowest one I've seen a picture of so far. Most are much wider. It's also a bit too tall for comfort.

Here are some evergreen options:

 Southern live oak - there are more vertical cultivars
 Red Bay (provided you don't have the Ambrosia beetle)
 Ubame Oak - evergreen
 Cherry Laurel 'Bright and Tight'
 Sweet Bays (Mag virginiana) mostly evergreen. 'Mattie Mae Smith' is a variegated one.
 Portuguese laurel
 Southern Magnolia 'Greenback' -- grows more vertical, nice light green on undersides of leaves - no russet coloring
 Oakleaf or Oakland hollies.
 Foster's holly (Sunny Foster has yellow tips, but slower)
 Ilex latifolia
 Ilex - Koehneana hybrids hybrids. Gorgeous lustrous  leaves, berries 'Hohman', 'Agena', 'Lassie'
 Red tips Photinia trained as a standard.
 Photinia serrulata (Chinese photinia)
 Osmanthus x fortunei (incredible fragrance in fall) - train as standard.
 Viburnum 'Chindo' very glossy evergreen small tree/shrub