Bearing in mind that existing non-caving-in structures are attached (however improbably precariously) to "the ground"[1], I can imagine three different types of ground-independence that (through single blocks or as full PSes, as described by the OP) could operate independently of this constraint without either caving-in or being in a world with cave-ins de-implemented via the Inits.
- Buoyancy relies upon some Dwarven Physics marking at least one block in the free-structure as "floaty" (air or water, or indeed magma) and at the same time both a "stable" block from which the rest of the structure can hang off without cave-in and (after accounting for the anti-buoyancy effects of the rest of the disconnected structure) is allowed to move according to the fluid flow and/or ultimate ability to float in the liquid. This could be the Dwarven equivalent of "liftwood" (anti-gravity material, al la 'Space:1889'), Cavorite ('First Men On The Moon', IIRC), empty (sealed) barrels built onto the side of the structure (your basic old-style raft design), or even something fancy like propulsion pods/nacelles in a more steam-punk/more-advanced situation, doing their bit to keep your submarine/airship from bottoming out.[2]
- Tethered structures would be similar except that a loose-link to an externally stable item(or, in more complicated systems, stable-by-proxy..?) would make the all blocks in the PS attached to the anchor point similarly cave-in proof. This could be rope (re-do an elevator as in a well, maybe even re-do the wells to be more like elevators!) or a full mechanical linkage (fortress raised off the ground by one more Z-level, assuming various other constraints aren't applicable). Should the rope/mechanism be broken, obviously there would be disaster (or general invonvenience).
- Resting-but-not-linking - It's all very well being able to raise a block above the ground, but if the adjacent blocks are treated (as they are now) as linked to the ground they're resting on, what happens? Do they lift off the ground, or does the raising block rise up and shove itself out of the ground-based structure around it? The answer is to have the equivalent of lego's "smooth bottomed bricks". A 2x2 with circular profile, pips above and rounded lower surface which is probably intended to slide over carpets, but also means that the model doesn't 'engage' with any scenery plates and become troublesomely fixed[3]. Currently, "connections that aren't connections" are limited to bridges, and of course Supports (once lever-dismantled) no longer connect. But not every situation works well with that scenario. A way of building blocks "on the ground" but intended to be moved in some way (slide horizontally, or by tether or buoyancy effect or mechanical linkage, lifted off of it) would enable some people's wish-list items. Yes, including titans, as you'd wish the leg to lift off (and be moved forward by various means) at certain points in the cycle, much the same as you might wish it to rest on the ground and itself do the lifting of the rest of the structure (and all other legs that are not currently lifting, and are likely pacing forwards even as the lifting ones are pacing backwards again), but without establishing "one-ness" with the ground that means it cannot lift up once more...
There's so many different answers, that I feel like encompassing them all, but certainly some summary of the above would be useful, rather than quoting it verbatim in some run-down of the issues. I'll leave that to people who think they understand what I've already said and think they can explain better, however.
[1] Or "the sky", according to some !!science!! I have seen reported.
[2] One possible example of the implementation of this principle would be to build a "lifeboat" room, attached to the ground by lever-linked supports and with a bridge between entry-door and the external (or similarly-airlocked) access point. Prior to the area it is in flooding (perhaps part of a defensive plan), the required occupants wander in, the door(s) ensured closed and then the water let in to the enclosing area to surround it to whatever degree is required. When the supports are remotely debuilt by lever (probably inside the structure), rather than fall through no support the "Empty barrels" or similar buoyancy aids built onto the structure (if the open space inside doesn't count, of course, which would depend on the application of Dwarven Physics to all such loose entities) immediately take over so that rather than caving in, the lifeboat room becomes an independent entity, floating slowly/quickly upwards, or whatever.
[3] Looking at it the other way, "smooth-topped tiles" would work as well on the ground, but then for a moving-fortress you've have to prep the ground ahead to stop your leviathon 'sticking', so I say you can build "smoothed-bottomed" ones, perhaps even different varieties (ones that slide sideways, and ones that just lift off but allow sideways force of sat on the ground).