It must have been observed, for example, that there was no element lighter than hydrogen or that there were not different-charged electrons (I believe the electron was discovered prior to Planck's Constant) but only one charge and that was the smallest charge. So was imagining that energy itself came in a smallest packet a huge surprise or was it confirmation of something that had already been theorized?
The quantization of energy of light of a given frequency into photons was a truly enormous leap from classical physics.
First, the ideas of atoms and elementary particles including electrons were being developed at the roughly same time as quantum mechanics. So the premise of the question is not quite right; the electron was discovered by JJ Thompson in 1897, and the charge by Millikan in 1913, while Planck's paper on black body radiation was published in 1900.
But even if we take for granted the existence of an electron with a unit charge, the quantization of energy is yet another major conceptual leap. Maxwell's classical theory of electromagnetism can very easily incorporate point charges$^\star$, and even if it does not explain why charges should come in units of the electron charge, there is no logical problem with there being a unit charge.
However Maxwell's equations make a very firm prediction that the energy of an electromagnetic wave is proportional to the amplitude of the wave, and the amplitude is a continuous quantity. There is no way to reproduce $E=\hbar \omega$ within classical electromagnetism; since accelerating charges produce electromagnetic waves, an charge oscillating at a given frequency can produce larger or smaller waves by increasing the amplitude of its oscillation. In classical physics, particles can oscillate with any amplitude. Thus there really is something extra and (from the point of view of classical physics) extreme that is needed to explain the black body radiation.
$^\star$ modulo issues regarding the self force, which I will ignore.
In early modern philosophy and science there was a corpuscular theory of light and Newton's authority was also behind it. At the end of the 19th c. electromagnetic phenomena demonstrated that light is a wave, but Planck's work seemed to vindicate the alternative view. Actually the constant was introduced as a mathematical trick - an integral diverges to infinity, while the corresponding sum is finite. Planck resorted to it in exasperation and later even said he regretted inventing this. But this view explains a lot more - something which could not and did not happen at once: there was no leap, only a gradual realization.
see Jammer M., *The Conceptual Development of Quantum Mechanics.* NY, 2nd ed. 1989. (There is also a scale problem : it took a generation and more to admit that quantum theory will stay, but from a distance it is a revolution.)