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 basic idea of general relativity is that a freely moving object follows a path through spacetime called a geodesic. By freely moving I mean the object experiences no force i.e. if you were that object you would be weightless just as if you were floating in space.
In flat spacetime geodesics are straight lines i.e. a freely moving object moves in a straight line at constant speed. This is just Newton's first law. However general relativity tells us that spacetime is curved due to mass, and in a curved spacetime geodesics are not straight lines. For example the astronauts floating around in the International Space Station are weightless because they are moving along a geodesic. However the mass of the Earth curves the geodesic so it goes in a circle round the Earth.
I'd guess (I haven't seen the video) that this is what Brian Greene is getting at. When we drop the ball and feathers we see them accelerate downwards. However if you were sitting on the ball or amidst the feathers you'd consider yourself to be weightless and not accelerating at all, just like the astronauts in the ISS do.
However if you whirl a stone on a string around your head, or drive a car round a roundabout, or any other form of rotational motion you are not following a geodesic. You know you're not following a geodesic because you can feel a force - the centrifugal force. This force is quite distinct from the gravitational force calculated using general relativity. It does not not have the same origin and it does not have the same effects. For example gravity causes time dilation, e.g. time runs slower near black holes, but the centripetal/centrifugal force does not cause time dilation.
Best Answer
I would say Brian Cox is being too cryptic. He is stating what is known as the Principle of Equivalence. In pure general relativity, gravity is not a force. It is the curvature of spacetime causing objects to obey the geodesic equation. This is a geometrical feature: the geodesic equation has no mass dependence. In free fall, the objects are unaware of their acceleration. In their frame the objects are at rest with respect to the rest of the universe. I think he is just saying that objects at rest behave the same. It's definitely not how the EP is usually stated.
EDIT: The title of the question has changed. A falling object (assuming complete free fall, i.e. no air resistance) does not experience a gravitational field. Suppose you are in a box and are dropped from a great height above the Earth. You want to test if you are moving. (Rather, you want to test if you are accelerating. Special relativity tells us we cannot test for absolute motion. Assuming a gravitational field that is sufficiently constant in a sufficiently small region of spacetime, the question of absolute motion is meaningless.) So you fire a laser from one side of the box to the other. If you are accelerating, the laser will appear to "curve." If you are in free fall, however, the photons from the laser will hit exactly where the laser is pointed. This is exactly the behavior of a laser one would expect moving at constant velocity in flat spacetime (i.e. no gravity). We then Lorentz transform to a motionless frame (the rest frame of the box). Thus free fall is in a sense equivalent to being stationary in a gravity-free spacetime.