Another reason not to replace with green or white ash: the emerald ash borer is marching across the country from the east. It is on Minnesota's doorstep now, and the insect wipes out the species (except young saplings) wherever it goes.
Paper birch will be way to susceptible to the bronze birch borer, unless you live in a cooler area that has lots of natural soil moisture, like next to a lake or marsh. River birch ought to do better. Red maples like the same conditions, too, but are more adaptable. Honeylocust, Red oak, white oak, Bur oak are good choices. Serviceberries (the tree type, not the shrubby ones) have lots of good attributes. Also look at Amur chokecherry. It has the most beautiful bark, nice fall color, spring flowers, not too much fruit and fast growing, but it is relatively shortlived (30 years).
