> ...I suspect the hot air balloon needed to hold up that rocket would be prohibitavely HUUUGE.
Correct. Therefore we go even further outside the box.
I envision a landing that goes about the same as now, except that the booster is halted about 30 meters off the deck instead of right on the deck. Then a giant (and well-padded) mechanical hand swoops in and grabs the booster, lowering it to the deck safe and sound.
If the aim or level is a bit off, no problem, the hand can compensate. As for engineering, well, the booster is mostly empty and not too heavy to contemplate holding up with a giant hand (or two). Of course it might get crushed a bit in the middle, but if it saves the engines...