I was meaning to discuss elegance in my essay, but I removed that section for lack of space, and because I thought it best to focus on the main argument. It is hard to pin down exactly what one means by an aesthetic notion like "elegance" in the context of mathematics and physics. My own feeling is that it has to do with economy and compactness of representation. That is, if we find a compact representation of physical laws that we can write down on a t-shirt, such as Einstein's equations, Maxwell's equations, or the Dirac equation, then I think we would tend to call that "elegant". As you suggest, the fact that we have laws of nature that are economical, work over a wide range of parameters, and are extremely precise, is what needs explaining.
Many of my computer science/information theory colleagues are wont to describe the elegance of physical laws in terms of algorithmic complexity, i.e. an elegant law is essentially the shortest computer program capable of generating the empirical data. Now, this cannot be anything more than a cartoon of what is actually going on. Algorithmic complexity is uncomputable in general and physicists are not in the game of writing short computer programs, at least that is not what they think they are doing. However, if I can argue that the social process that generates human knowledge would tend towards generating such a compact representation then we have our answer.
Now, codes for data compression and error correction that asymptotically achieve Shannon capacity have been developed which have the structure of scale-free networks. Since data compression provides an upper bound on algorithmic complexity, which is exact in several cases like i.i.d. data, it is at least possible that the human knowledge network has the structure of an optimal compression of the empirical data, or that it is tending towards such a structure. (This is part of what I meant by describing the knowledge network as "efficient" in my essay.) For this I have to argue that the social process of knowledge growth would tend to generate such a structure. It is fairly easy to argue that a compact representation of at least the hubs of a network is something that people would spend a lot of effort trying to achieve, since compact representations encompass a wider range of phenomena in a small number of laws. They are also more reliably generalizable, because each law encodes a larger number of empirical regularities that have been observed to hold.
My argument then is that the laws of nature are not elegant because of any special property of physics, but rather that, in any universe, physicists would spend a lot of effort trying to compactify their description of whatever the physics is. For example, although Maxwell's equations look very compact in their modern Lorentz covariant form, in fact there are a lot of background mathematical definitions and concepts required to state them in this form. Without those, they look more complicated, as in their original integral form. This is a clear example of a case where the same physical laws went through a very conscious process of compactification. I would argue that something like this is playing a role every time we develop an "elegant" set of physical laws.