Dear Alexey,
I agree with your sentiment, but unfortunately "beauty" is a bit too subjective of a premise to start with when looking for an objective explanation. Even "simplicity" and "elegance" have subjective aspects, but maybe "efficient" is the right starting point. We humans (or at least some of us) find it beautiful when a very wide range of phenomena can be explained with a few efficient concepts. Asking why this is in fact the case is an excellent question, but I wouldn't say it's the key part of the mystery.
I say this because even if I provided a good explanation for why there are a few rules that explain everything, that would really only apply to the most fundamental physics from which everything else emerges. Such an explanation wouldn't cover higher-level, effective- or emergent- physics, for which mathematics is certainly still important, and this mysterious overlap between math and physics continues. I would say that the most use of higher-level math actually takes place at this higher level, where any "ultimate efficiency" arguments don't really apply.
Furthermore, I'm convinced we haven't gotten down to the truly fundamental level yet, in any of our theories except maybe perhaps GR. So at this point, I see pretty much all of physics as a higher-level approximation, and speculating about the efficiencies of the fundamental level that may be waiting for a discovery is just... well... speculation! :-) Although I am convinced, as are most physicists, that any ultimate explanation will indeed be efficient.