The Redemption of Christopher Columbus by Orson Scott Card is a fairly interesting time travel story, though I felt it ultimately fell short on addressing the most intriguing questions it posed.
In particular, Card sets up a moral dilemma: is the misery of countless generations justified by the resulting society? If the resulting society develops technology which would change that prior misery, but would result in the extinction of that future society (disregarding the paradox involved), do they have a moral justification to do so?
On a lighter note, I've forgotten, did we already cover Niven's
Rainbow Mars in this thread? Really a collection of extremely silly time travel stories, loosely strung together into a book. Great fun.