To rephrase all of this in yet another way:
If God is All Good, he is not at all bad. This would entail that He does nothing that is bad.
If God is All Powerful, then he can do anything that it is logically possible (or at least physically possible) to do.
Allowing Evil would be bad. If the holocaust* was bad, then (if there is a God,) God allowed it (even if he did not cause it). If God allowed a bad thing, He was either not All Good, or was unable to stop it.
One would assume that it was indeed both logically and physically possible to stop the holocaust.
It might be that free will is more good than all the bad stuff in the world is bad. Therefore God would allow fee will, in turn allowing us to do bad stuff -- even really bad stuff. Could it be the case that free will is worth this? And if free will is so important, then why am I denied the power that Hitler was given? Surely we all deserve the same freedoms... And I do not have the power to do what Hitler did. God seems to be limiting my actions more than He limited Hitler's! This implies that he could have stopped Hitler without limiting his free will or that my free will is limited.
It might also be that we cannot know what good is without seeing what bad is. But surely we don't need as much bad as there has been to know what good is? Sticking with the holocaust as an example: the people who were killed were not helped to see what good was by the addition of gruesome death into their lives. Nor were the killers. And I don't think it helped me, either. I can know good without genocide to compare it to. Even a murder might be more than I need. (And why do some people suffer so much more than others? Do they deserve to know more good?)
And if all this evil is okay in God's eyes, why should we trust him anyway?
*I'm using the holocaust to represent thousands of years of evils. The holocaust itself it only a very small fraction of the unnecessary pain and evil that has been.
Goneaway: We are starting the assumption that we know something about God. I think this is an assumption that most Christian/ Muslim/ Judaic people would support. We know both that He is good, and we also know what good is. (If we didn't know what good was, we could not act morally. It is assumed that we can be moral.)
Piq: If heaven is there to balance out the suffering that we undergo during our lives, doesn't that imply that someone who suffers more gets a better heaven? Well, that wouldn't actually bother me, although I'd like the chance to choose whether I get a good life and a mediocre afterlife, or a terrible life and great afterlife. Maybe I did get that choice, and I just don't remember.
But that wouldn't change anything! God, being all powerful and all good, should decide to give us all great lives and great afterlives. Surely He can? Yes, suffering builds character, and maybe we all need some character, but we don't need to starve to death when we're three, or be tortured and killed for trespassing, or born with fatal genetic defects. That's just redundant.
But wait, you say! (Well, you didn't, but I bet you would if I let you get a word in edgewise). Being thankful for what you have is Good, and you can't be thankful unless you have an example of the Bad Stuff that you don't have. So yes, some people get the short end of the stick, but it benefits the majority. Well... Yes, but this leads us to a very odd conclusion: for us to be thankful, these bad things don't actually have to happen; we only have to believe that they really could happen. And the best way to put these scary ideas into our heads is to have people tell us that they are happening, or have happened. But only a particularly cruel and/or stupid god would actually have these things happen. He's way powerful enough to make us think that they happened, even though they didn't. And even though I now know that if I believe in a good, all-powerful God, I can rest assured that no-one ever suffered any more than that time I got second degree burns on my arm, I'm still thankful that I'm not living in the midst of a battle field or being burned as a witch. It works! Clever, sneaky God. He was doing right by us all this time, and we doubted him!