Why not something like this (assume image is split into image 1, 2, 3 and 4, left to right):
How it is
When attempting to build on an incline (figure 1), currently the game finds some average height, plops the building on that height, and proceeds to flatten the terrain around the building (figure 1). This results in these tiny portions of terrain to get extreme angles (red in figure 2), which can prevent further building and/or even prevent units from moving through previously passable terrain.
Currently proposed solution
In figure 3, we can see the 'skew the building to follow the terrain' that has been worked on. As most will agree, it looks odd. But it does fix the problem of not altering the topography.
Maybe this
Figure 4 holds my idea. The idea is you pick the highest edge-point of a structure, and use that as the structure Y position. Rather than highest edge-point, you could also find an average which is heavily biased towards higher-Y points (meaning it will be partially sunk, but mostly 'floating' above the lower parts of the slope). You then add a 'base' to the structure (blue in figure 4), so as it would not look like it floats - kinda like what naval factories do atm, with their 'infinite' legs that go down as deep as need.
Pros are you benefit from 'not altering terrain' while also not skewing the buildings.
A big con is you somehow need to model to 'extend' below it's usual lowest Y value. But I thin that, with diligent work, just extending the base of all non-floaty buildings to go down shouldn't be a big problem. The only problematic buildings are the unit-dispensing ones, where there would be an odd ledge the unit would have to cross - one solution is to just extend the existing ramp to also cover negative Y space, but it might look awkward if the ramp is on a similar angle as the terrain (it might extend like 3 unit widths away from it's usual terminating point, which would look like it's going under other buildings).