Could you describe your reaction a little more? As a Haldeman fan who isn't generally a fan of time travel, I've been willing to pass on it, but I'm curious. If Haldeman's hitting on all cylinders I probably don't want to miss it.
Re: the Mars trilogy, which others have mentioned, I was very disappointed in that - I was hoping it would be an epic classic of the 90s and he certainly seems to have devoted enough research to make it so but (IMO) the plot was lacking, the characters were lacking, and the politics were overwhelming - and he lets the amount of research show through and drag down the very very long books (and I generally love tech-wonk SF). The first one was probably the best of them though and has one of the casually funniest lines I've read (the "One small step for man" moment, Mars-style).
For those who've read the book but still don't know what I'm talking about:
*spoiler* The main character becomes the first human to set foot on Mars and, when he does so, says... "Well. Here we are." *end spoiler*
Methusaleh's was good. IIRC, it's probably as laconic and plot-driven a Lazarus tale as there is and the best intro.