Why do the flap maneuvering speed margins to stick shaker depend on altitude?
It's because the air is thinner, meaning the dynamic pressures are reduced for a given velocity through space, but the inertial mass of the air frame is the same as at sea level. Or you could flip it over and say the inertial effects (true airspeed) are higher for the same indicated airspeed (dynamic pressure). In other words, the dynamic forces have less influence over the inertial forces for a given velocity and mass. As well, the thrust margins to accelerate out of a stall are also less.

Best illustration is to take it to an extreme.  Say you are at 45000 ft, flying near stall at 150kt indicated.  That is, the dynamic pressures of the air are equivalent to 150kt at sea level. However, your actual velocity through space is roughly 300kt, so all of the inertial forces are effectively doubled relative to the aerodynamic forces, and on top of the that, you have more or less zero thrust reserve. You now have WAY less stick shaker margin, and a stall at that altitude requires extreme responses (aggressive dives to gain speed).

In your case, the effects are a lot more subtle, but still significant, especially approaching 20000 ft.