When using Mercurial I sometimes find that it is hard to understand the relationship between changesets when there are thousands of changesets, and sometimes ten or more active branches at any one time. Currently, I use hgview which is okay, and while it makes a reasonable attempt to represent the parent relationships it is still basically one dimensional. I imagine something making use of graph visualisation programs such as GraphViz might work nicely, or perhaps something more wacky.
Currently I'm working on projects with around 30,000 revisions, and I expect that number to grow significantly; if 100 full time developers really grok distributed version control and start committing regularly and sharing their full development history then we could end up dealing with millions of revisions. A browser which doesn't have to load the entire history in to RAM every time you want to look at it therefore becomes necessary
I'm interested in good history browsers for any version control systems as well, especially if there is a chance I can port them to Mercurial.