Personally I would like some way to navigate through the whole thread in some sort of reasonable order. My preference would be depth-first with the leaves sorted by the most recent post /in that subtree/. This matches how tools like newsreaders and Mutt will sort threads, and I believe how Gmane worked as well. (Though I will admit that for something like a web site that does not keep the state of whether posts are read or not, reordering leaves like that may be confusing. In a tool like Mutt it is useful behavior as when new posts come in they will naturally gravitate to the bottom [or top, depending on your sort order] of your message list).
In particular I'd like to be able to, starting with a particular post, repeatedly hit "next" and be assured that once I hit the next sibling post to the original I've read that entire subthread. Gmane let you do this just by whacking the space bar; if you weren't at the bottom of a post it would page down, if you were it would go to the next one.
In other words I'd like it to behave as much like a good NNTP newsreader as possible.