I give an historical flavor of where the idea of $E=h\nu$ even comes from. In doing so, I hope to convince the reader that Planck's construction of the theory from first principles was significantly more important than coming up with the right formula for the spectral distribution of a blackbody; it was these ideas which ultimately led to the requested energy/frequency proportionality.
It was Kirchhoff who (quantitatively) proposed the so-called blackbody problem ~40 years earlier c.a. 1859 (a year after Planck was born) . The model he used, which was subsequently borrowed and further developed by Planck, involved a simple hollow container with a small hole into which one applies e/m radiation. Kirchhoff put forward the law that range and intensity of radiation inside this container is purely dependent on temperature - totally independent of its constituent material and dimensions. Any radiation escaping through this hole captures a sample of all wavelengths present inside the container at a given temperature and so acts as a model of a perfect blackbody.
After a surge in the electrical industry (the invention of the incandescent lightbulb, arclight, etc.), there was a competition to produce the best and most efficient lightbulbs (c.a. 1880's) which as you can imagine helped to spark interest from more theorists and experimenters tremendously.
Wien is credited with a first theory in understanding the spectral distribution of a perfect blackbody which works just fine when you don't consider IR frequencies. After experimental error was found with Wien's proposal (which took a couple years), Planck was the one to correct the formula as was nicely described in this answer by OON. He was not, however, happy with just writing down a formula which seemed to work. He spent a hard six weeks trying to derive it from first principles and develop a deep understanding of what it meant.
A theoretical interpretation therefore had to be found at any cost, no matter how high.
Source: Hermann (1971) quoted p. 23. Letter from Planck to Robert Williams Wood.
In doing so, he needed a way to get the right combination of frequencies and wavelengths. The model which led to the energy/frequency proportionality $$E\propto \nu $$ was treating the walls of the blackbody consisting of a series of oscillators, each of which omitting just one frequency. If each oscillator is treated as a spring with a different stiffness (spring constant), then each would have a different frequency and heating the walls was apropos to setting the springs in motion (at the correct temperature) as well as modeling the absorption/emission of radiation. The idea was that, with a constant applied temperature, over time the system would reach thermal equilibrium.
Simultaneously (as well as a little earlier) Boltzmann was developing the kinetic theory of gases using probability theory and Planck (firmly not an atomist) borrowed a notion from Ludwig Boltzmann to consider discretized energy levels - whom Planck acknowledged largely for his theory. I list a noted quote from Boltzmann from a conference in 1891
I see no reason why energy shouldn’t also be regarded
as divided atomically.
it is borrowed from here Ludwig Boltzmann - A Pioneer of Modern Physics. Getting back to oscillators, Planck found the amount of energy emitted from his oscillators to be dependent only on their amplitude. With his formula as a guide and this new explanation together, the energy per oscillator was forced to be divided into quanta of chunks $h\nu$ with proportionality constant $h$ which Planck referred to as the quantum of action. One of the first to acknowledge the significance of what Planck had done with this energy quantization was Einstein who is commonly attributed with saying it would require a re-writing of the laws of physics and no doubt inspired him to envision the photon or quantum of light which led to the celebrated wave-particle duality.