If you are hoping for a gas that can compress to exceed water density without itself condensing into a liquid, my guess is that the search will be difficult if not impossible. Uranium hexafluoride at 5 bar and $120^\circ C$ is a gas that is denser than liquid hydrogen for example but LH2 cannot exist in this condition. I would be interested to know which gas less dense than water can be compressed over the density of water without liquefying. Someone with more experience in chemistry should be able to prove why such a gas doesnt exist.
You will have to accept that the only way for a balloon to sink as it goes deeper is for the gas inside to liquify as it achieves depth/pressure, thereby shrinking the balloon and increasing its density over that of the water it is submerged in. The alternative is to go so deep that the water itself freezes and traps the balloon in place (but that violates the spirit of the question if you ask me, even more so than condensation of the gas!).
With water it is even more impossible to find such a gas for the air bubble (I am now venturing a little bit into chemistry). $H_2O$ is a very special molecule in that it has extremely high intermolecular interactions (Hydrogen bonds) for such low molar mass--basically it takes up very little space (very high density) despite its simplicity as a compound. When considering a balloon gas of similiar chemistry, a suitable candidate molecule is ammonia $NH_3$ which is gaseous in room conditions and relatively easy to condense by pressure, but in liquid form is still nowhere near as dense as water ($0.667x$ at $500 bar$) despite the similar molar mass.
I tried sulphur hexafluoride $SF_6$, a gas famous for its high density--the phase diagram suggested that condensation could occur at $0^\circ C$, or $273K$ at around $15bar$. The difficulty is obtaining the density of liquid $SF_6$ at this temperature. My source suggested $1.98x$ relative density (relative to water) at $50^\circ C$ and $1.33x$ at $25^\circ C$. With the lack of data, a manual extrapolation would place liquid $SF_6$ at less dense than water if temperature was $0^\circ C$, i.e, the balloon would not sink. The source suggests however that given a $150m$ deep tank with water at least $25^\circ C$ $SF_6$ will produce the phenomenon of a balloon sinking at that critical depth.
But I wasn't satisifed. There had to be a molecule that was gaseous as room conditions, liquified easily, and had molar mass higher than water. That molecule is 1,1,1,2-Tetrafluoroethane, a CFC gas--which I realised was similar to ammonia in that they are both refrigerant gases. Tetrafluoroethane doesnt have those hydrogen bonds, but because of the very electronegative fluorine atoms only on one side of the molecule, there are some very strong dipole interactions (easy to liquefy this gas). And of course, the high molar mass means the liquid form is likely to be denser than water. 1.295x density of water at just 3 bar, $0^\circ C$. At $25^\circ C$ the required pressure rises to 6.6bar, but relative density is still >1.2x.
So if you ever get your hands on a balloon full of nasty HFC-134a refrigerant, you don't have to dive deep to see something really cool, like a floating balloon suddenly collapsing at a critical depth and starting to sink.