Tl,dr: Entropy is the right definition, because it's incredibly useful in the description of statistical and thermodynamic systems. Whether or not it quantifies "disorder" in whatever sense of the word is completely irrelevant - it just so happens that it can be interpreted that way.
Entropy is not a measure of disorder. At least not really. Then again, if you count information theoretic entropies, there is more than one entropy.
Let's start with the classical definition: A very useful thermodynamic concept is that of a heat engine. This is a contraption, which can transform heat energy into work or vice versa. When considering such heat engines, it turns out that while energy conservation is undoubtly necessary, it is not enough to fully describe heat engines. In particular, it doesn't really capture irreversibility. It was then realised (by Clausius) that you also needed what today is known as the second law of thermodynamics and with it, entropy. In short: entropy is conserved for irreversible processes. This implies that entropy is the right physical concept: it correctly classifies heat engines according to their capabilities and it can correctly predict reversibility in isolated and closed systems (among other things).
Shortly thereafter came Boltzman's statistical definition. Given a macroscopic state, it counts the number of microstates that a system can possibly be in and weighs them according to their probability. The more microstates a system can be in, the higher its entropy. Now if you posit that any microstate is (a priori) equally likely, this will give you the definition of Boltzman's statistical entropy. In view of a better microscopic understanding of the world, Boltzman saw the need to describe macroscopic systems in terms of their microstates. On the one hand, since the number of microstates is huge (sometimes formally infinite), this is a hopeless undertaking. On the other hand, not every single aspect of the microscopic world will result in a differen macroscopic behaviour, so there is hope that you can capture the microscopic properties in a few simple measures that you can then use to derive the macroscopic (thermodynamic) entropies such as temperature, volume, etc. This is essentially why entropy was introduced.
The beautiful thing is that the two definitions turn out to be consistent.
This is essentially, where you have things backwards: Entropy is not supposed to be a measure of disorder, it rather happens to be a measure of disorder in the precise sense that a system is more disordered, if the number of microstates that lead to a given macroscopic state is large and their probabilities are close to equidistribution. In this sense, a solid state is more disordered and a gas is less disordered, because in a crystalline solid, the number of configurations of the atoms is clearly more limited.
In other words: The precise meaning of "disorder" in thermodynamic systems is defined via entropy and not the other way round. The reason that makes physically sense is that entropy is not (a priori) meant to be a measure of disorder. Entropy is used to a) quantify reversibility/irreversibility in heat engines, and b) define useful quantities for macroscopic systems based on only the microscopic states of the system. The fact that the second law exists can be seen as one possible "proof" that entropy is the right definition: it captures an extremely important concept in our theory of the world.
Further notes: As I said, there are other entropies - especially in information theory. They are various measures of how much information content a system has or how much information is accessible, etc. While they are very useful in information theoretic contexts (the Shannon entropy for instance characterises the maximum lossless compression rate without prior knowledge), it is not always clear how these entropies relate to statistical physics and it is an active field of research.
