Is there anything natural about the principle of "stationary action"?

I want to get some things out of the way, but feel free to jump to the section 'What the action is' as that section is the business end of this answer.

Hamilton's stationary action can be explained in terms of Newton's second law. Then again: in itself that does not necessarily say much: in any logical system there is great freedom to interchange axiom and theorem. (This interderivability is also discussed by SE contributor knzou in an answer about derivability in physics )

Classical mechanics has various ways of expressing the physics taking place, and as we know they are interderivable. They are mathematically equivalent, so on that basis alone we don't have the means to judge which way of expressing the physics is the more fundamental.

The reason the work-energy theorem is referred to as a theorem (rather than principle) is that Newton's second law and the work-energy theorem are mathematically equivalent (as in: it's not another principle).

The second thing to get out of the way:
It is sometimes suggested that the concept of stationary action is accounted for in a deeper way in terms of quantum mechanics. However, as we know: when quantum mechanics was constructed the only way to make progress was to try only ideas that give formula's such that at macroscopic scale quantum mechanics reproduces classical mechanics. In order to make progress any trial formula that was found to lead to violation of the work-energy theorem was dropped. Ultimately, to suggest that quantum mechanics explains the work-energy theorem is circular reasoning.

What the action is

In the image below the curves represent the case of an object being thrown upwards against a potential that gives a 2 $m/s^2$ acceleration: it rises and descends again.

Black curve: trajectory of the object
red curve: kinetic energy
green curve: minus potential energy

When you sweep out a range of trial trajectories the curves of the energies change accordingly. (Further down is an animated GIF, 7 frames, 3 seconds per frame, that displays the process of sweeping out variation.)

The image displays the point in variation space where the trial trajectory hits the true trajectory: then the red curve (kinetic energy) and the green curve (minus potential energy) are parallel to each other.

So: what you need is a method to know where the slopes of the red/green curves are not equal, and where they are.

To that end we use the following property of the value of an integral: when the slope of a curve changes the value of that curve's integral changes in proportion. (The necessary and sufficient mathematical condition for that property is that the start point and the end point of the curve are fixed.)

In the image below the curves on the left are the same as the curves of the first image. The curves on the right are the corresponding functionals.

In the example presented here the potential increases linear with height. The green line on the right shows how the integral of the minus potential energy responds to variation of the trial trajectory. In this case the green functional is a straight line because in this case the potential energy increases linear with height. The red functional represents how the integral of the kinetic energy responds to variation of the trial trajectory. Since the kinetic energy is a quadratic function of the velocity the red functional is a quadratic function of the variational parameter.

There is only one point where the respective values of the two integrals change at the same rate (changing in opposite direction). That point is the point where the trial trajectory hits the true trajectory.

We see that 'stationary action' is purely a mathematical tool. The physical property that it corresponds to is the work-energy theorem: at every moment in time the rate of change of kinetic energy must be equal to the rate of change of minus potential energy.

Another way of seeing that 'stationary action' is purely a mathematical tool: the extremum that you find arises from the following two mathematical inputs that have no physical counterpart: the constraint that the start point and the end point are fixed, and the operation of integration.

This particular example was for the simplest case: a potential that increases linear with height. The reasoning generalizes to all cases.

An animated GIF, showing how the curves representing the energies respond to variation of the trial trajectory. The slider changes the variational parameter.

(The images illustrating this answer are my own work, they're from my own website.)