No, there is no "fallacy" in perceiving it this way, the sleight of hand is rather in the presentation. Two types of effects, which often work in concert, conspire to create this perception of "inevitable simplicity" of the solution. I will illustrate with examples from mathematics. In a post Coming up with short “magical” proofs on Math SE a user shared their frustration with one of them:
"As I have spent more and more time studying mathematics, I see more of these "magic" solutions in which some obscure identity or property is pulled out of nowhere and used to facilitate a proof...often, multiple such jumps are used in a proof...and these proofs are meant to be done in an hour or so. I feel discouraged by this, because I don't understand how to do these "magical" things."
But unless one tried their hand on it first, and only read a textbook or class presentation, they may not even notice the work done by such tricks. Textbooks tend to "prepare the ground" beforehand, or at least to smooth out the emergence of a key idea in the course of proof. The real, conceptual, difficulty in coming up with them is swept under the rug and obscured in presentations whose authors are aware of them from the start. But textbooks are often cleaned up imitations of what happens historically. Some initially tough problems are solved by what Grothendieck called the "rising sea", see McLarty, Rising Sea: Grothendieck on simplicity and generality:
"The unknown thing to be known appeared to me as some stretch of earth or
hard marl, resisting penetration... the sea advances insensibly in
silence, nothing seems to happen, nothing moves, the water is so
far off you hardly hear it... yet it finally surrounds the resistant
substance... [The theorem] is submerged and dissolved by some more or less
vast theory, going well beyond the results originally to be established".
The core difficulty in the original problem is in the absence of a framework, a paradigm of concepts and intuitions, that serves as a scaffolding for scaling it. And it recedes as the framework advances. This happened to many Archimedean and Apollonian intricate demonstrations after the development of coordinate geometry, calculus and algebraic methods, or to Gödel's incompleteness proofs within the modern mathematical logic, see Has any 'difficult' proof ever been superseded by a 'simple' one? Peirce talked about theorematic (vs corollarial) proofs as introducing
"something not implied in the conceptions so far gained, which neither the definition of the object of research nor anything yet known about could of themselves suggest, although they give room for it".
But when the paradigm is already established "the conceptions so far gained" make all the difference. Modern expositions tend to present even the original problem as already immersed into a framework designed to "submerge and dissolve" it. Notation and terminology are modernized so that they already by themselves suggest a path forward. "Proper" intuitions are reinforced and contrary ones suppressed or dimissed. What appears as an "obscure identity or property" to the uninitiated often becomes a prominent structural element in this risen sea. The aberration of historical development that results, and the impression of "inevitability" created when such modernizations are taken at face value are well known to historians.
A nice illustration of this is the story of counting infinities, see Is there an alternative to Cantor's cardinalities that makes proper subsets smaller than their sets? Since before Aristotle philosophers and mathematicians alike struggled with comparing and quantifying infinities, and grasping the nature of the continuum. It was not until Cantor at the end of 19th century that the issue was finally settled, more or less. Yet Gödel, writing in What is Cantor’s Continuum Problem? (1947), claimed just the "inevitable simplicity" of Cantor's solution:
"Closer examination, however, shows that Cantor’s definition
of infinite numbers really has this character of uniqueness. For whatever
“number” as applied to infinite sets might mean, we certainly want it
to have the property that the number of objects belonging to some class
does not change if, leaving the objects the same, one changes in any
way whatsoever their properties or mutual relations (e.g. their colors or
their distribution in space)... So there is hardly any choice left but to accept Cantor’s definition of equality between numbers, which can easily be extended to a definition of “greater” and “less” for infinite numbers..."
But it is exactly over definitions of equality, and the paradoxes of infinity they lead to (such as the equation by 1-1 correspondence of infinite wholes to their proper parts), that philosophers and mathematicians argued over for centuries. It is not that the original difficulty has disappeared, but rather that it was shifted to selecting a particular paradigm. A textbook or a class teacher is already committed to a paradigm, the modern one, and inculcates the reader/listener in it step by small step, hence the difficulty becomes invisible.
Still, as it turned out pace Gödel, the modern paradigm for infinities and the continuum is not the only possible one.