It's also worth noting that when you do Galileo's Tower of Pisa experiment, the heavier object does land first. (You think you release them at the same time, but you don't - your muscles let the heavier object go first.)

I find sometimes we here denigrate our distant predecessors too much; I have heard well-educated people call the Greeks fools for rejecting heliocentrism, despite the fact that the Greeks had powerful arguments against heliocentrism like the lack of stellar parallax, or we mock them for the 5 elements, despite the incredible feat of devising atomism just by considering basic logical paradoxes caused by alternative ontologies.

Aristotle really said it, in Heavens 4.2:

For any two portions of fire, small or great, will exhibit the same ratio of solid to void, but the upward movement of the greater is quicker than that of the less, just as the downward movement of a mass of gold or lead, or of any other body endowed with weight, is quicker in proportion to its size.

Note that he take the extreme position that heavier objects fall faster, not just denser! This claim is robust against translation errors since he is keeping the material fixed. I have not been able to find the passage you mention, though I did find a discussion of objects falling slower in water than air.