How about honeylocust, such as Gleditsia 'Shademaster' (green) or 'Sunburst' (yellow)? They're pretty tolerant trees and when they shed their leaves they are just dropping small leaflets. They grow fairly fast too.
I also like the Amur maple as Frillylilly suggested but they tend to be multi-stemmed which it doesn't sound like you would want?
BTW are you sure the black spots on the maples are caused by mites? Around here we get a lot of "tar spot" on maples, a fungal disease.
