"QM works in the Hamiltonian picture and I recall from my undergrad days that you get there from a Legendre transformation on the Lagrangian (or something to that effect) so I'm trying to understand the justification of that approach before moving up the conceptual ladder."

That is only one approach to QM. As you rightly point out, Hamiltonian and Lagrangian approaches are always two sides of the same coin: one is only the Legendre transformation of the other and so they describe the same physics.

So to that end there is a neat QM Lagrangian representation: the path integral formulation. You can apply it to basic QM as well as to QFT or even QFT in curved spacetimes and string theory.

So if your goal is to "trace your way from simple postulates", that is a good way: assume your system can be described by an action, and go from there. It works in pretty much every scenario. In most research I've been involved, you always end up constructing generic actions whose coefficients eventually determine the behaviour of the theory.

And to get back to what I assume is your real conundrum (why do we extremize something to begin with), I just don't think there's any true answer as to why nature behaves this way.

What we can answer is: what is the action, what does it represent, what does it mean to extremize it? The short answer to this (provided by the path integral formulation I mentioned earlier) is that the action is essentially controlling a probability distribution of paths in a given geometry. In quantum mechanics, we interpret this distribution with that of actual particles. When you extremize the distribution, you essentially find the most likely trajectory, and if your distribution is peaked enough around that trajectory, then you can take this path as representative of your system when fluctuations are ignored.

So in the classical limit of QM, that trajectory is all that's left (and that would be the classical mechanics trajectory).

Interestingly a similar interpretation exists in statistical physics. If you "complexify" your time dimension, your action is again on a Euclidean (instead of lorentzian) spacetime and the time direction behaves like a circle whose radius sets a scale akin to a temperature. This might sound a bit complex but where I'm going with this is that once again, you can think of this euclidean path integral as a distribution of paths over fluctuations (this time thermal), and the extremum is this time the system's behaviour when at equilibrium.