The following answer is a bit "intuitive" but hopefully still mostly correct, or at least thought provoking. Sorry for the lack of rigor. I plan to write down these thoughts one day into some nice blog post, this is just a rough sketch.
I am not sure but the biggest point in the concept of "Hamiltonian" is that two independent systems Energy are additive.
Non interacting systems can be described by H1+H2.
I searched this page and this has not been described.
Why is this additivity such a big deal ?
Let's take a harmonic oscillators.
The phase space is a circle's circumference.
Energy is proportional the radius of the circle.
So the circumference.
So the number of microstates.
So S=-log(E)*c.
So why is this a big deal ?
Because if we take two harmonic oscillators, then the entropy becomes additive (extensive).
So why is this such a big deal ?
Probability. Independent systems log likelihoods are additive.
So, the physical independence and the probabilistica independence in this case are the same.
So statistical physics becomes possible to "be done".
This is a different take on the accepted answer's statement. From an information theoretic point of view.
Why is independence such a big deal ?
The Kolmogorov complexity of the algorithms that describe the phase space, or even the motion are additive. So it is optimal. In the sense of Occam's razor.
Hence the Hamiltonian formalism is the most optimal way to create theories that describe independent systems.
From this point of view it is intuitive to see that perturbation theory "works".
If the change in energy of one subsystem is small (weak perturbation) then the phase space does not become much larger, so the information to be stored to describe the perturbed system is not much more because the size of the phase space does not change much.
So this information theoretic approach gives an intuitive explanation why perturbation theory "works".
Also, E=mc^2 follows from this (up to a constant). E=mc^2 is simply expresses that if one oscillator disappears then it's phase space disappears too, and the energy is transferred to the other oscillator, so the information is conserved. E=mc^2 is "simply" about conservation of information. Without the concept of Hamiltonian this equation and the corresponding conservation of information would not exist.
So the Hamilton equation is important because it makes it possible to treat independent systems independent in the information theoretic (from which follows probabilistic) frameworks, as this was hinted at the first point in the first answer. Statistical mechanics is based on this. Also, thermodynamics would not exist with the concept of Energy. Since independent systems are described by their energy which is extensive, additive.
Interestingly, all extensive variables in thermodynamics are related to changed of the phase space. Volume grows, volume related phase space changes, kinetic energy decreases (momentum related phase space decreases), in adiabatic systems, so that the total information content stays constant (and consequently the entropy).
So without Energy there is no Entropy, no information, no phase space, no E=mc^2.
Why ? Without Energy there is no independence between isolated systems.
Why is that wrong ? Theories (algorithms) that describe independent systems have additive Kolmogorov complexity. Without the concept of Energy theories would not have this property hence would not obey Occam's razor, hence would be unnecessarily more complex than needed. Would be less correct.
In the framework of Solomonoff's theory this statement can be justified.