Location We See in the Movies are very politically different
For one thing, a major reason for the overwhelming anti-Empire bias might simply be a side-effect of the locations we see in the Prequels (Coruscant and the Senate) vs Original Trilogy (mostly Outer Rim and Rebel-Allied/Friendly planets and locations).
Unhappy Senators and Influence of the Rebel Leaders
But, while the Galactic Empire began with thunderous applause, even at that point of time, not all Senators were happy - the existence of The Delegation of 2000 means there were at least 2000 Senators and top diplomats opposed to the Palpatine's growing powers. While many were arrested and more removed their support from the Petition of 2000 as the Clone Wars came to an end, many of the remaining were the ones who went on to found and support the Rebellion in 18 BBY, just a year after the Empire (most prominently Bail Organa and Mon Mothma).
Given their persistence and determination, and since they continued to hold positions in the Imperial Senate, it is unlikely that they would have given up spreading their views even outside of the Rebellion, however covertly, in the 20 years between the end of the Prequels and the start of the Original Trilogy.
More Time for the Empire's true Colors to be Revealed
In the time between the end of Prequels and the Original Trilogy, just from the information available from the movies themselves, we know that:
Palpatine finally dissolved the Imperial Senate.
The Empire showed that they could and would destroy a whole planet, without warning even if they were legally a member of the Empire. And this was not some small Outer Rim crime-ridden hell hole no one would care about, but Alderaan, a Core World planet renowned throughout the galaxy "for their planet's unspoiled beauty, refined culture, and commitment to peace".
Alderaan's destruction would not only have instantly made most surviving Alderaanian hostile to the Empire (specially since the truth was successfully spread galaxy-wide by the Rebels) but also shown other planets that giving in to the Empire was no guarantee of safety from annihilation.
If we take information from the EU, protests started up not long after the formation of the Empire, when the Empire turned out to be a rather pro-Human (and discriminatory towards Non-Humans, an in-universe explanation for the mostly human structure of the Empire is the CGI-less OT).
There are many other instances of atrocities committed by the Empire in the EU, such as the Ghorman Massacre, where a non-violent protest was brutally crushed (Literally. They landed a ship on top of them). This was an early atrocity, which apparently explicitly led the Remnants of the Delegation of 2000 to form the Rebel Alliance.
Given the early date of the Massacre (it happened barely a year into the Empire), it seems likely that it was just the first of many such massacres and atrocities, each of which would continue to turn people against the Empire.
The Empire didn't actually die out with the Emperor
As for talking about the time at which everyone is the Galaxy might have started distrusting the Empire, it probably didn't happen for years after Endor, because according the EU the collapse of the original Galactic Empire only really happened almost a decade after the OT (which makes sense, given how large the Empire was, and how many powerful Imperials bureaucrats and generals would still have been left all over the Galaxy post-Endor) and the reorganized Imperial Remnant persisted for decades still.