I would imagine that Gondor, especially in places like Dol Amroth, is fairly densely populated, at least relatively speaking. I'd also assume this of Harad. These areas were spared the worst of the fighting between Sauron and Gondor. The reason much of Eriador is underpopulated has to do with Arnor being completely destroyed, including being overrun by Angmar a few times, and suffering the plague. Gondor was not the focus of Angmar, so remained relatively intact. Cardolan and Rhudaur, especially, bore the brunt of the Witch-King's wrath, and never recovered.
Minas Tirith seemed underpopulated because people tried to stay away from it as Sauron's power grew in Mordor; for example, remember how the various forces sent by the provinces of Gondor just before the Battle of Pelennor Fields were seen as being too few? Not because the forces weren't there; it was because the bulk of the fighting strength was kept at home because Minas Tirith was looking like it would fall.
I think there were a few areas of Middle Earth that were fairly well populated: Dale and Erebor, northern Mirkwood, Dol Amroth, Harad, Rhun, and a lot fo Gondor's coastal area besides Dol Amroth. The Shire, of course, was also pretty well-populated. I'd also imagine there was at least a good number of Dwarves in the Grey Mountains.
I think another good indication of Gondor's and much of the former Arnor's population density is the fact that Aragorn rebuilt the northern kingdom pretty early on in the Fourth Age. There had to be people there to populate it.
I think the reason Middle earth seems so underpopulated is because we see so much of what was once Arnor, which, as I noted above, still hadn't recovered from millennia of war. If the Fellowship had trekked through southern Gondor, I think we'd have a different impression.
Just my thoughts on the subject.
