The statement that all objects fall at the same rate on the earth (more accurately, with the same acceleration) is an idealization that relies on two approximations. Both approximations are excellent for objects of humanly manageable size and mass near the surface of the earth, but both approximations fail for something with the size and mass of the moon.
The first approximation is regarding the size of the falling object. This approximation assumes that the objects have negligible size compared to the scale over which the gravitational field varies. Near the surface of the earth, the "acceleration of gravity" on the far side of a 1-meter diameter ball is almost identical to the "acceleration of gravity" on the near side, so the statement applies quite accurately for objects of humanly manageable size.
However, this approximation is not true at all for something the size of the moon that is nearly touching the earth (say, with only 100 meters between their surfaces), because then the force on the moon due to the earth's gravity is much less on the far side of the moon than it is on the near side of the moon. 
The second approximation is regarding the mass of the falling object. The statement that all objects fall at the same acceleration on the earth also assumes that the acceleration of the earth due to the gravitational field of the falling object is negligible. This approximation isn't very good for the earth-moon system even when they're far away from each other. If the earth and moon started at rest at some large distance away from each other, they would both accelerate toward each other (because the moon pulls on the earth, too), thus decreasing the distance between them more quickly than if only one of them were accelerating. This more rapid decrease in distance causes an more rapid increase in their mutual attraction, which would not occur if either body were replaced by a feather.
A mathematical analysis of this second point is given in another post:
Don't heavier objects actually fall faster because they exert their own gravity?