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.