It comes from Maupertuis’ work in the 18th century (about a century before Hamilton). The initial insight is that a physical object follows the “shortest” possible “path”, in the same way as light follows the quickest path as in Descartes’ law. The difficulty is that the path is in a phase space with more than our usual 3 dimensions, so the whole thing is a bit abstract and calculations are a bit counter-intuitive at first. The approach is still useful because it helps solving problems that are very difficult to solve using Newton’s equations, like systems with constraints or couplings between objects.

> The whole notion of "action" feels entirely foreign and unintuitive for someone who's just studied Newtonian mechanics.

Action is a tool to calculate these shortest paths, and because the actual trajectory corresponds to an extremum of the action, and most of the time to a minimum, the principle is sometimes called the “least action principle”. Fundamentally, that’s almost all there is to it. The rest is defining the action, and processing it to get equations of motion. Action kind of looks like a weird energy in classical mechanics,

It is foreign from Newtonian mechanics. If you want to understand how it works you need to consider Lagrangian mechanics, which was a generalisation of Maupertuis’ principle and paved the way for Hamiltonian mechanics (which are another step in abstraction). Newtonian mechanics are built on calculus and the concept of derivative; Lagrangian mechanics are built on variational calculus and the concept of functionals.

> At least I've never managed to find a real world feel for what it is, unlike with force or energy.

Action is actually quite similar to energy, conceptually. Energy is whatever gets minimised in a Newtonian system at equilibrium. Energy changes are governed by differential equations that we can solve to calculate simple trajectories. Action is a function that is minimised along the trajectory of a physical system.

This approach is extremely powerful. The same principle can be used to derive the equation of motion for systems following classical or quantum mechanics, or general relativity by “simply” considering different definitions for the action (or, equivalently, different definitions of what we call the Lagrangian function, which is more common). It’s a bit difficult to explain more in this format; if you want to dig deeper you should start by looking into Lagrangian mechanics.