The best murder mystery I have ever feasted upon appears in Vernor Vinge’s Across Realtime in the last story of the book: Marooned in Realtime. Now reprinted, be warned it is easier to follow if you have the Across Omnibus which contains The Peace War and The Ungoverned.
Finally, and in my opinion the crown jewel of the book, comes Marooned in Realtime, a masterfully plotted mystery story spanning 50 million years into the future. Marooned in Realtime is centered around Wil Brierson and a small band of friends trying to restart the human race in a post-post-apocalyptic world of decaying high-technology. Marooned is so excellent that it alone is worth the price of admission.