Suppose the balloon with air (A) weighs $m_a$ and the balloon with concrete (B) weights $m_b$. The force accelerating the balloons downwards is $m_a g$ for A and $m_b g$ for B, where $g$ is the acceleration due to gravity. In the absence of air the acceleration is simply this force divided by the mass, so both balloons accelerate at the same rate of $g$. So far so good.
Now suppose the air resistance is F. We don't need to worry exactly what F is. The force on balloon A is $m_a g - F$, so its acceleration is
$$ a_a = \frac{m_a g - F}{m_a} = g - \frac{F}{m_a} $$
and likewise the acceleration of balloon B is
$$ a_b = \frac{m_b g - F}{m_b} = g - \frac{F}{m_b} $$
So the balloons don't accelerate at the same rate. In fact the difference in the accelerations is simply
$$ \Delta a_{ba} = a_b - a_a = \frac{F}{m_a} - \frac{F}{m_b} $$
Since $m_b \gg m_a$ the difference is positive, i.e. balloon B accelerates at a much greater rate than balloon A.
Response to comment
I think there are a couple of possible sources of confusion. Let me attempt to clarify these, hopefully without making things even more confused!
Firstly the air resistance affects both the acceleration and the terminal velocity. I've only discussed acceleration because terminal velocity can get complicated.
Secondly, and I think this is the main source of confusion, the gravitational force on an object depends on its mass while the air resistance doesn't. However the air resistance depends on the velocity of the object while the gravitational force doesn't. That means the two forces change in different ways when you change the mass and speed of the object.
Incidentally, Briguy37 is quite correct that buoyancy has some effect, but to keep life simple let's assume the object is dense enough for buoyancy to be safely ignored.
Anyhow, for a mass $m$ the gravitational force is $F = mg$ so it's proportional to mass and it doesn't change with speed. Since $a = F/m$ the acceleration due to gravity is the same for all masses.
By contrast the air resistance is (to a good approximation) $F = Av^n$, where $A$ is a constant that depends on the object's size and shape and $n$ varies from 1 at low speeds to 2 at high speeds. In your example the size and shape of the ballons is the same so $F$ just depends on the speed and for any given speed will be the same for the two ballons. The deceleration due to air resistance will depend on the object mass: $a = Av^n/m$, so air resistance slows a heavy object less than it slows a light object.
When you first release the balloons their speed is zero so the air resistance is zero and they would start accelerating at the same rate. On the moon there is no air resistance, so the acceleration is independant of speed and the two objects hit the ground at the same speed.
On the Earth the acceleration is initially the same for both balloons, but as soon as they start moving the air resistance builds up. At a given velocity the force due to air resistance is the same for both ballons because it only depends on the shape and speed. However because acceleration is force divided by mass the deceleration of the two balloons is different. The deceleration of the heavy balloon is much less than the deceleration of the light balloon, and that's why it hits the floor first.
From the way you phrased your question I'm guessing that and answer based on calculus won't be that helpful, but for the record the way we calculate the trajectory of the falling balloons would be to write:
$$ \frac{dv}{dt} = g - \frac{Av^n}{m} $$
This equation turns out to be hard to solve, and we'd normlly solve it numerically. However you can see immediately that the mass of the object appears in the equation, so the change of velocity with time is affected by the mass.
Assuming that the three objects you speak of are point particles initially positioned pretty much right next to each other, then all three objects will hit the earth at the same time.
From newton's law of gravitation, we have:
$F = \frac{Gm_1m_2}{r^2}$ and where $m_1$ is the mass of the Earth, and $m_2$ is the mass of an object away from the Earth (e.g. feather, or O1).
To obtain acceleration of the object (e.g. feather), we divide by mass, so:
$acceleration = \frac{Gm_1}{r^2}$
As we can see, the acceleration of the feather only depends upon the mass of the Earth. Therefore, the feather and object O1 and the elephant will all accelerate towards Earth at the same rate.
However,
O1 has a very large mass, and this will cause the Earth to accelerate towards O1. But since all three objects were initially positioned in the same spot, and all three objects are accelerating towards Earth at the same rate, the three objects remain next to each other, and therefore when the Earth reaches O1, it will reach the feather and the elephant at the same time.
Best Answer
The acceleration due to gravity $g$ on a sphere of radius $r$ with mass $M$ is given by $$g = GM / r^2$$ where $G$ is the universal constant of gravitation.
The volume of a sphere is given by $$V = \frac43 \pi r^3$$ and density $\rho$ is given by $$\rho = M / V$$ Combining those equations and eliminating $r$ we get $$g = G \left(\frac{4\pi}{3}\right)^{\frac23}M^{\frac13}\rho^{\frac23}$$ So if mass is constant and density is doubled, gravity is scaled by $2^{\frac23}$, or approximately 1.5874. So if you did this to the Earth $g$ would go up from $9.81ms^{-2}$ to $15.57ms^{-2}$.