What's a good explanation for stalemate being a draw for a beginning chess player? I've started playing chess a little more using an app on my phone, and frequently run into the situation where I'm dominating the computer opponent (on an easy difficulty level) to the point where he can't make a legal move (e.g. I've got 5 queens or something like that).  Of course, this is a stalemate and it's a draw.

From Googling around, it seems like it's common for most beginners to feel like they're being "cheated" in this situation (as I do), while most experienced players "agree" with the rule.  

I've yet to see an explanation that makes me feel like I'm not being cheated.  The explanations all seem to say "it's a draw because the rule say it's a draw", or only slightly better, "the rules say that to win, you must put your opponent into check (such that he can't get out), and since you didn't do this, you didn't win, so it's a draw."  I don't mean any offense, but this just seems like circular reasoning to me.

Draws make intuitive sense to me when there are few pieces left and neither player has enough of an advantage to checkmate the other (a simple example would be when there are just 2 kings left), but I'm having a hard time seeing how "anywhere I move would put me in check" and "I'm in check and anywhere I move would leave me still in check" aren't really equivalent concepts.

Take the theoretical case above (say black has 5 queens and a king, and white just has a king, and they're positioned in such a way that white can't move without putting himself in check).  How can a beginner be convinced that black hasn't dominated so thoroughly that he should win?
If you were dominating so much, you should have checkmated him. It's not the fault of the game that your mistakes may mean you don't win.

The appeal of chess comes partly from the fact that it is hard. One of the reasons for that is that there is quite a large drawing margin -- you may have a great position at some point, but there may still be many ways to defend tenaciously in endgames, and a good opponent can make it very hard for you to win even if he does make a big mistake early on.

Those ways include eternal check, the fact that you can't checkmate with a single bishop or knight against a lone king, fortresses, and also many ways to defend based on stalemate.

For instance, king + pawn vs king (where the pawn isn't immediately lost) would be a trivial win for the pawn without stalemate, but with stalemate it's sometimes a forced win and sometimes it's possible to hold a draw. Because you need to see which it is before you trade down to that endgame, that makes the game deeper and harder.

I don't think chess would have become as popular as it is without rules like stalemate. It would be a shallower game.

You just didn't play well enough.