I think Gondor also had a navy, since they defeated the Corsairs a few times. It may not have been as strong as it was during the War of the Ring. Most of the other nations in LOTR were landlocked. Lindon was beside the sea, but the Elven ships were geared more towards providing an exodus for the Elves than getting involved in military matters.
By the late Third Age, the only great mariners in western Middle-earth seem to have been the Gondorians, the Sindar of the Grey Havens and the Corsairs of Umbar. The Haradrim do not seem to have had a navy of their own, but were likely allied with the Umbarites (including what was left of the Black Númenóreans). There might have been Easterling navies, but they might not have found with worthwhile to sail around Far Harad. Perhaps the passage was too hazardous.