Don't heavier objects actually fall faster because they exert their own gravity?
Using your definition of "falling," heavier objects do fall faster, and here's one way to justify it: consider the situation in the frame of reference of the center of mass of the two-body system (CM of the Earth and whatever you're dropping on it, for example). Each object exerts a force on the other of
$$F = \frac{G m_1 m_2}{r^2}$$
where $r = x_2 - x_1$ (assuming $x_2 > x_1$) is the separation distance. So for object 1, you have
$$\frac{G m_1 m_2}{r^2} = m_1\ddot{x}_1$$
and for object 2,
$$\frac{G m_1 m_2}{r^2} = -m_2\ddot{x}_2$$
Since object 2 is to the right, it gets pulled to the left, in the negative direction. Canceling common factors and adding these up, you get
$$\frac{G(m_1 + m_2)}{r^2} = -\ddot{r}$$
So it's clear that when the total mass is larger, the magnitude of the acceleration is larger, meaning that it will take less time for the objects to come together. If you want to see this mathematically, multiply both sides of the equation by $\dot{r}\mathrm{d}t$ to get
$$\frac{G(m_1 + m_2)}{r^2}\mathrm{d}r = -\dot{r}\mathrm{d}\dot{r}$$
and integrate,
$$G(m_1 + m_2)\left(\frac{1}{r} - \frac{1}{r_i}\right) = \frac{\dot{r}^2 - \dot{r}_i^2}{2}$$
Assuming $\dot{r}_i = 0$ (the objects start from relative rest), you can rearrange this to
$$\sqrt{2G(m_1 + m_2)}\ \mathrm{d}t = -\sqrt{\frac{r_i r}{r_i - r}}\mathrm{d}r$$
where I've chosen the negative square root because $\dot{r} < 0$, and integrate it again to find
$$t = \frac{1}{\sqrt{2G(m_1 + m_2)}}\biggl(\sqrt{r_i r_f(r_i - r_f)} + r_i^{3/2}\cos^{-1}\sqrt{\frac{r_f}{r_i}}\biggr)$$
where $r_f$ is the final center-to-center separation distance. Notice that $t$ is inversely proportional to the total mass, so larger mass translates into a lower collision time.
In the case of something like the Earth and a bowling ball, one of the masses is much larger, $m_1 \gg m_2$. So you can approximate the mass dependence of $t$ using a Taylor series,
$$\frac{1}{\sqrt{2G(m_1 + m_2)}} = \frac{1}{\sqrt{2Gm_1}}\biggl(1 - \frac{1}{2}\frac{m_2}{m_1} + \cdots\biggr)$$
The leading term is completely independent of $m_2$ (mass of the bowling ball or whatever), and this is why we can say, to a leading order approximation, that all objects fall at the same rate on the Earth's surface. For typical objects that might be dropped, the first correction term has a magnitude of a few kilograms divided by the mass of the Earth, which works out to $10^{-24}$. So the inaccuracy introduced by ignoring the motion of the Earth is roughly one part in a trillion trillion, far beyond the sensitivity of any measuring device that exists (or can even be imagined) today.
The paradox appears because the "rest frame" of the Earth is not an inertial reference frame, it is accelerating. Keep yourself in the CM reference frame and, at least for two bodies, there is no paradox. Given an Earth of mass M, a body of mass $m_i$ will fall towards the center of mass $x_\textrm{CM}=(M x_M + m_i x_i)/(M+m_i)$ with an acceleration $GM/(x_i-x_M)^2$. Note that $\ddot x_\textrm{CM}=0$
Really we have only hidden the paradox, because of course $x_\textrm{CM}$ is different for each $m_i$. But this is a first step to formulate the problem in a decent inertial frame.
The paradox resurfaces again if you want to get rid of $(x_i-x_M)$. In most applications, now that you are in a non accelerating reference system, you want to consider distances related to it, ie $x_i-X_\textrm{CM}$. The solution is to redefine the mass. As $x_i-x_\textrm{CM}= M (x_i - x_M) /(M+m_i)$, we can say that the object $i$ falls into the Mass Center with an acceleration $G{M^3 \over (M+m_ i)^2}{1 \over (x_i-x_\textrm{CM})^2}$ You could say that the actual mass of the "earth at center of mass" is this correction.
Once you are into the trick of changing the value of the mass, you can still stick to the reference frame of the earth. In this reference frame the quotient between force and acceleration is $Mm_i/M+m_i$ You can claim that this is the actual mass of the body during the calculation. This is called the reduced mass $m_r$ of the system, and you can see that for small $m_i$, it is almost equal to $m_i$ itself. You can ever write some of the previous formulae using the reduced mass $m_r$ in combination with the original masses, for instance the above ${M^3 \over (M+m_ i)^2}= M {m_r^2\over m^2}$, but I am not sure of how useful it is. In any case, you see that you were right about the "heavier implies faster" but that it is perfectly managed.
For three objects, m_1 and m_2 falling into M, the question is how to compare the case to m_1+m_2 falling into M. You separate the forces between internal, between 1 and 2, and external, against M. Look at the point $x_0= {m_1 x_1 + m_2 x_2 \over m_1+m_2}$ . This point it is not accelerated by the internal forces. And the external forces move them as $$\ddot x_0={1 \over m_1+m_2} \left(m_1 {G M \over (x_1-x_M)^2} + m_2 {G M \over (x_2-x_M)^2}\right)={F_1+F_2 \over m_1 + m_2}$$
This is becoming long... ¡I can not put all the Principia in a single answer!. So you can forget all the previous stuff, consider it is just to a mean to fix notation and get some practice, an read the answer:
If the two bodies are at the same distance $x$ of the "external" earth, they suffer the same external acceleration $g=GM/(x-x_M)^2$, and the same happens with $x_0$. If both bodies are in an approximation where $g$ can be considered constant, which was the case originally considered by Galileo (and the modern $g=9.8~{\rm m/s^2}$), then they have the same acceleration -and also the combined position $x_0$-. If they are not at the same distance nor in an approximation of constant -equal everywhere- field, then you can still save the movement of $x_0$ to work as if it were a gravitational force for some single mass $m_T$, but then the manipulation of the equations will produce in the relative positions of $x_1$ and $x_2$ some accelerations of the order of $1/(x_0-x_M)^3$. Such forces are the "tidal forces".
In addition to the already given answears this also might be of interest:
When hammer and feather are dropped simultaneously they arrive at the same time, when dropped independently the hammer attracts the planet more than the feather, so you are right, the total time until impact is then smaller for the hammer.
If you pick up the hammer and let it fall to the ground while the feather lies on the ground and its mass adds to the planet's mass (neglecting desity inhomogeneities) it takes the same time as when you pick up the feather and let it fall down while the hammer is on the ground and its mass adds to the planet, since m1+m2+m3=constant.
When you drop hammer and feather simultaneously, the feather will travel the longer distance in the same time, and is therefore faster than the hammer, since the planet is moving more towards the hammer than to the feather, and the feather is attracted by the largest sum of masses.
The initial distance of the point masses is 1 meter; in the first example you have 1000kg vs 100kg vs 1kg and in the second one 1000kg vs 666.̇6kg vs 500kg. As you can see the "hammer" and the "feather" arrive at the same time:
