I've had my own idea about the main issue with boats specifically which I haven't seen resolved here or elsewhere yet, but forgive me if someone else came up with this solution:
How could DF detect that something is a boat/buoyant if it is constructed dynamically of walls etc.?
My solution builds on a notion the game must already implement: natural connectedness. Basically, right now there exists some algorithm (albeit probably not a particularly efficient one) which, whenever a tile with a wall/construction changes, checks adjacent tiles to check to see if they are adjacent to a tile that has support. This type of checking has to go out until it reaches a tile on the edge of the map. Edge tiles are marked as "naturally connected" (I'm not Toady, so I'm not 100% on this, but this is the natural way to implement cave-ins as they currently exist).
This could be extended to have a third kind of tile - a "weakly connected" one. Normally a tile flagged as weakly connected does nothing, however if it gets flagged as NOT connected to a "naturally connected" then it tabulates all the tiles that it is connected to, detects water below it, and does whatever calculations are necessary. Subsequently (to prevent repeated recalculation on every frame) another flag could be set on the rest of the structure's tiles to ensure that they don't collapse like normal constructions.
How such a tile could be designated is a question of algorithmic choice - it could need to be set by the player, or possibly be flagged as the first tile that does the check for its own connectedness.
In any case, the problem of how to make the thing move isn't answered, and might end up being complicated (even though I seem to remember Toady saying something about possibly reusing some old code from adventure mode for shifting tiles and their information...).