I definitely would recommend these books by Vernor Vinge:
- "Marooned in Realtime"
spans 50 million years, from the near future to 50 million A.D. - epic!
- "A Deepness in the Sky"
takes place thousands of years in the future
- "A Fire Upon the Deep"
takes place 30000+ years in the future