What actually IS action? I am delighted that the the whole of physics derives from a single simple principle. Since the time of Lagrange, the principle of least action has not only become the founding principle of classical mechanics (supplanting Newton’s laws), but it readily became the basis of electricity and magnetism (in the 19th century) and quantum physics (in the 20th century).  It is wonderful that everything in the universe follows laws which come from a single principle. All I ask is that such a principle is one which I can understand – or, at least, one for which I might develop some feeling. But it's hard to get a good physical intuition for action. In particular, why should it be the kinetic energy minus the potential energy, instead of plus?
What is the physical interpretation of action?
 A: Ok, I will preach before I teach. 
So, why is acceleration meaningful? If I adopt your scornful tone, I can say, "What? Second derivative now? Why not take a third? Or a fourth? Did Newton just keep trying until he found a derivative for his formulae which would give Keplerian orbits?" Ok, I am admittedly being a little hyperbolic. But the point is that a principle is supposed to be meaningful if it entails a small set of propositions that can produce a plethora of true statements about the universe. The principle of least action is the epitome of this project in classical mechanics. So, it has to be given its due beyond comparing it to something that Lagrange would have come up with measuring his foot ;) 
Now, having said that, I cannot agree with you more. The ultimate job of physics is not just to describe nature (however succinctly) but to explain it. I'll make an argument from authority here and notice that this is something Weinberg has iterated many times. So the sentiment that physics is supposed to explain why things happen and not just describe what happens is not a naive sentiment. 
So, why does the action principle work? There is no ultimate explanation for it in classical mechanics. One can formulate it in many different ways but the argument ultimately is that the proposition is true because it produces Newtonian laws which we know to be true. The explanation as to why on earth something like the action is relevant to physics comes from, you guessed it right, quantum mechanics. In particular, from the path integral formulation. The story goes, the quantum mechanical propagator is given by $$\int\mathcal{D}[q(t)]\mathcal{D}[p(t)]e^{\frac{i}{\hbar}\int dt( p(t)\dot{q}(t)-H(p(t),q(t)))}$$where the integration is over all paths in phase space subject to the initial and final conditions on the $q(t)$. If the Hamiltonian is "nice enough", i.e., simply put, if it is in the form $\frac{p^2}{2m}+V(x)$, then we can perform the explicit integration over the momenta and get that the propagator is given by 
$$\int\mathcal{D}[q(t)]e^{\frac{i}{\hbar}\int dt\big[ \frac{\dot{q}^2(t)}{2m}-V(q(t))\big]}$$
This is the famous path integral formulation of quantum mechanics where there is some probability associated with each path that a particle can take (denoted by the summation over all paths $\mathcal{D}[q(t)]$ in our expression). The classical limit of quantum mechanics is obtained by taking the limit of $\hbar\to0$. However, we cannot exactly take this limit because $\hbar$ is dimensionful in our formalism and thus, we can only compare it to something. So, the natural thing to do is to say that  $\frac{1}{\hbar}\big[ \frac{\dot{q}^2(t)}{2m}-V(q(t))\big]\to\infty$. This is legitimate because of the fact that now we are taking the limit of a dimensionless quantity. As you can see, this limit means that the phase of our integrand is wildly oscillating and almost all contributions will cancel one another. But, the only contributions that would survive are the ones when the phase is not wildly oscillating. When would this happen? When the phase is stationary with respect to changes in the path. Or, in other words, when $$\frac{\delta }{\delta q(t)}\int dt \bigg[ \frac{\dot{q}^2(t)}{2m}-V(q(t))\bigg]=0$$As you can see, this is exactly the action principle of classical mechanics which says that the classical trajectories obey such an equation. 

It goes without saying, all of this is super handwavy. For a detailed discussion, see, for example, Chapter 6 from Srednicki's book which he has kindly availed freely on his website. 
