One could explain "well, gravity is the curvature of spacetime due to the mass-energy". But that would only lead to "well, why does mass-energy curve spacetime?" And, should someone produce a proposed answer to that, the follow-up question would have to be "but why is that so?" etc.
At some point though, one must accept that there are genuine fundamentals, genuine primaries that cannot be explained in terms of something "more" fundamental, "more" primary.
Gravity is considered one of those fundamentals. But the question "what is the reason for gravity" presumes that gravity isn't fundamental. So, the only proper "answer" to your question is "to the best of our knowledge, gravity is fundamental".
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.
Best Answer
Just consider the water, due to gravitational attraction(which I'm not sure how effective it is in this case); water molecules like to be as close to each other as possible. This means that they like to push the bubbles as close to each other as possible. Since the air has negligible mass, its gravitational forces can be neglected compared to the water ones.
The other way to go through this reasoning is by what has been suggested in the question, i.e. assuming the bubbles have negative mass. This solution has few steps, as following:
Say we have a huge spherical lump of water(with the radius $R$), without any bubbles inside. The gravity potential of this sphere is $\frac{-3GM^2}{5R}$, but we are not going to use that.
Now, say we don't remove a small spherical part(radius $r$ and mass $m$) of the water and replace it with a same-sized sphere with density $\rho'$(or mass $m'$) but rather add it to the current sphere(a ghost like sphere which can only interact through gravity with the world). To calculate the gravitational force acting on this sphere using Shell's theorem, we also need to know the distance from the center; assume it's $x$. Since the sphere had been in equilibrium before, the new net force will be(note the force should be proportional to the mass of each object):
$$ -\frac{GM'(x)}{x^2}m' \tag{1}$$ where $M'(x)$ is the mass of water inside a sphere with radius $x$.
$$F_1=-\frac{GM'(x)}{x^2} m' - \frac{G m' m'}{(2x)^2} \\ F_2=\frac{GM'(x)}{(x)^2} m' + \frac{G m' m'}{(2x)^2}$$
Or the accelerations:
$$a_1=-\frac{GM'(x)}{x^2} - \frac{G m' }{(2x)^2} \\ a_2=\frac{GM'(x)}{(x)^2} + \frac{G m' }{(2x)^2}$$
$$a_1=-\frac{GM'(x)}{x^2} + \frac{G m }{(2x)^2},$$
($M'(x) \gg m$)which is towards the center(and the other sphere). So it looks like the two spheres are attracting each other.
Now there are some ambiguities here:
Also I should point, if the bubbles get in touch; they will immediately collapse into a single bubble. This is due to the surface tension, not the gravitational effects for sure.