Two uses of version control seem to dictate different checkin styles.
distribution centric: changesets will generally reflect a complete feature. In general these checkins will be larger. This style is more user/maintainer friendly.
rollback centric: changesets will be individual small steps so the history can function like an incredibly powerful undo. In general these checkins will be smaller. This style is more developer friendly.
I like to use my version control as really powerful undo while while I banging away at some stubborn code/bug. In this way I'm not afraid to make drastic changes just to try out a possible solution. However, this seems to give me a fragmented file history with lots of "well that didn't work" checkins.
If instead I try to have my changeset reflect complete features I loose the use of my version control software for experimentation. However, it is much easier for user/maintainers to figure out how the code is evolving. Which has great advantages for code reviews, managing multiple branches, etc.
So what's a developer to do? Checkin small steps or complete features?
The beauty of DVCS systems is that you can have both, because in a DVCS unlike a CVCS, publishing is orthogonal to committing. In a CVCS, every commit is automatically published, but it in a DVCS, commits are only published when they are pushed.
So, commit small steps, but only publish working features.
If you are worried about polluting your history, then you can rewrite it. You might have heard that rewriting history is evil, but that is not true: only rewriting published history is evil, but again, since publishing and committing are different, you can rewrite your unpublished history before publishing it.
This is how Linux development works, for example. Linus Torvalds is very concerned with keeping the history clean. In one of the very early e-mails about Git, he said that the published history should look not like you actually developed it, but how you would have developed it, if you were omniscient, could see into the future and never made any mistakes.
Now, Linux is a little bit special: it has commits going in at a rate of 1 commit every 11 minutes for 24 hours a day, 7 days a week, 365 days a year, including nights, weekends, holidays and natural disasters. And that rate is still increasing. Just imagine how much more commits there would be if every single typo and brainfart would result in a commit, too.
But the developers themselves in their private repositories commit however often they want.