It's not out of thin air, it's from a very empirically successful theory: Maxwell's electrodynamics. The problem back then was that this theory was not relativistic, i.e. the speed of electromagnetic wave in Maxwell's equations was the same under all reference frames. So you either abandon the idea that laws of physics remaining the same under all reference frames, OR abandon Galilean velocity addition.
Einstein's approach was modifying the latter so that it fits with the former, by imposing invariant speed. This was written in Einstein's original paper. It's not a mystery assumption.
It's also a very common procedure: two empirically successful theories have conflict and you need to resolve them by building something larger than both and reducing to both under limit.
I also agree we have gained insight into how kinematic structure is derived from algebra + physical constraint. Though you still need the physical insight to choose which physical constraint.