The underlying data structures do matter, even with mercurial. One workflow I immensely appreciate with Git is locally committing some series of messy changesets and commit messages and then afterwards, when I have finished the feature, tidying everything up by rewriting the history (git rebase -i) before I push my commits.

When I tried the same approach with mercurial I found that rewriting the history is not reasonably supported by mercurial. They use these append-only data structures that sound nice, because they assure stability (no already written data is ever in danger because files are only appended) and fit with the general concept of commit->pull->merge. But when you want to change the commit history you clash with the append-only concept. The Histedit extension which is meant to provide this feature has warnings all over the place that what I do is dangerous and might result in data loss with changeset backups written to locations in the working tree. It's horrible compared to Git.

Now don't misunderstand me, Git has a lot of problems UI wise (for example I still don't really grasp what is going on with detached heads). But I find the fundamental design choices more sound than with any other VCS that I have tried.