Why do two bodies of different masses fall at the same rate (in the absence of air resistance)?
it is because the Force at work here (gravity) is also dependent on the mass
gravity acts on a body with mass m with
$$F = mg$$
you will plug this in to $$F=ma$$ and you get
$$ma = mg$$ $$a = g$$
and this is true for all bodies no matter what the mass is. Since they are accelerated the same and start with the same initial conditions (at rest and dropped from a height h) they will hit the floor at the same time.
This is a peculiar aspect of gravity and underlying this is the equality of inertial mass and gravitational mass (here only the ratio must be the same for this to be true but Einstein later showed that they're really the same, i.e. the ratio is 1)
Newton's gravitational force is proportional to the mass of a body, $F=\frac{GM}{R^2}\times m$, where in the case you're thinking about $M$ is the mass of the earth, $R$ is the radius of the earth, and $G$ is Newton's gravitational constant.
Consequently, the acceleration is $a=\frac{F}{m}=\frac{GM}{R^2}$, which is independent of the mass of the object. Hence any two objects that are subject only to the force of gravity will fall with the same acceleration and hence they will hit the ground at the same time.
What I think you were missing is that the force $F$ on the two bodies is not the same, but the accelerations are the same.
There are two ways that mass could effect the time of impact:
(1) An object which is very massive has a stronger attraction to the earth. Logically, this might make the object fall faster and so reach the ground sooner.
(2) An object which is very massive is difficult to get moving. (I.e. it has very high inertia.) Thus one might logically expect the very massive object to be more difficult to get moving and so to lose the race.
The miracle is that in the world we live in, these two effects exactly balance and so the heavier mass reaches the ground at the same time.
Now let me give a simple explanation for why it's natural that this comes about. Suppose we have two very heavy masses. If we drop them separately they take some time T to fall. On the other hand, if we attach them together, will they take the same length of time? Think about a sphere split into two halves:
Two two halves of the sphere would fall at the same speed as each other. So if you dropped them next to each other, they'd fall together. And dropping them next to each other isn't going to be any different from screwing them together and dropping them together. That is, there won't be any force on the screws. So the combined (or screwed together) sphere has to fall at the same rate as the split sphere.