One of my reference books has the following listed as "tolerant of road and sea salt":
Acer tataricum ssp ginnala, Amur maple
A. triflorum, Three-flowered maple
Alnus glutinosa, European alder
Amelanchier canadensis, Juneberry
Betula nigra, River birch
Carya ovata, Shagbark hickory
Ginkgo biloba, Gingo
Gleditsia triacanthos var. inermis, Thornless honey locust
Gymnocladus dioica, Kentucky coffee tree
Koelreuteria bipinnata, Chinese goldenrain tree
K. paniculata, Goldenrain tree
Lagerstroemia indica, Crape myrtle
Malus spp, Crabapples
Nyssa sylvatica, Tupelo
Ostrya virginiana, Ironwood
Phellodendron amurense, Amur cork tree
Prunus cerasifera, Purple-leaved plum
Prunus maackii, Amur chokecherry
Prunus sargentii, Sargent cherry
Prunus serrula, Paperbark cherry
Sophora japonica, Japanese pagoda tree
Styrax japonicum, Japanese snowbell
Tilia tomentosa, Silver linden
Ilex opaca, American holly
Magnoia grandiflora, Southern magnolia
Prunus carolianiana, Carolina cherry laurel
I didn't double check all the tree's hardiness zones. There were other trees in the list but I left out larger maples, ash (due to EAB potential), oaks (too large), any tree with significant fruit mess. Some of the prunus and malus sp now have cultivars which bloom but do not have significant fruit.
Hopefully this may give you a start.
Sylvia