FWIW, an experiment I made once (in my final thesis for design school) was to have the TOC in the form of a vertical ruler of sorts, showing main chapters and subsections, on fold-out flaps in the front and back:

Each line in the «ruler» corresponds to one spread; the vertical position of the page numbers on the pages would correlate with this. Since this was printed digitally it all wasn't as precise as I'd have liked it, but I still found it interesting as a way to map out one's position in the text relative to the chapter structure; and it was interesting to be able to make visual cross-references, using arrows pointing to the referenced spread in the TOC (as can be seen in the photo).
BTW, the text dealt at least in part with linearity, nonlinearity, and cross-linking techniques, so this «navigation» was sort of a meta-statement in itself.