Since the church pretty much controlled government and the printing press, how did Luther, Calvin et al get the word out? Since literacy was so low, how did they spread the 95 Thesis in such an effective way? Was the idea of indulgences really so unpopular? It seems that it would be popular with anyone that had money and wanted to have a little fun with no after-life consequences.
First, the church didn't control governments; that's false, and there was a great deal of church-state tension throughout all Christian Europe. The only areas directly administered by the church were the Romagna, Avignon, and some cathedral towns, but even in the cathedral towns, control over the bishops who ruled from the cathedral was contested between ecclesiastical and secular powers.
As a result there were always rulers for whom the reformation of the church was irrelevant, or something they actively supported. The Elector of Saxony was (I believe) the earliest secular ruler to shelter Luther; by the time the Holy Roman Empire cared enough to bring military power to bear, the reformation had spread enough that there were a number of Protestant princes in Germany, who formed the Schmalkaldic league.
Also remember that the reformation was a struggle within the church, not from outside it. The leaders of the reformation were mostly ordained priests and monks. In many senses the reformers were more fervently religious than the secular, not to say libertine, papal court. There had always been factions within the church, on questions of practice, theology, and international politics; and in this case whole institutions went over to the Reformation, and supported it.
Where both the local government and the church were unfavorable, the reformation spread by lay preaching. Lay preaching was unusually effective in part because, at the beginning of the reformation, authorities loyal to the pope would banish lay preachers for a first offense, rather than imprisoning or executing them. This created a sort of contagion, as it forced protestants activists to keep moving, bringing their message to new cities.
This answers part of your question about literacy - as with any religious movement, oratory was very important. But also remember that it was possible to print tracts or even gospels illegally, or to smuggle them from pro-protestant cities. Literacy was high enough that there was an audience for vernacular scriptures. Of course, this audience was larger in literate urban areas.
Indulgences were unpopular for exactly the reason you cite. Devout Christians, especially in Germany, felt that they were making a mockery of biblical teachings about sin.