Hmm, I'd say that of long-distance space travel and time travel, time travel is the more improbable. But there are high-power physics brains that can make either of them look doable, and doubtless interrelated.
Relativity
Causality
Faster-than-light/timetravel
Pick any 2.
FTL is basically the same as timetravel in that according to relativity the time dilation caused by speed can result in some strange phenomena. The basic example is that an observer observing someone going at FTL can see him arrive before he sees him depart with the correct frames of reference.
Though this would only appear as time travel to an outside observer, never to the person going FTL. (yeah, it's hard to imagine)
Anyway, i'd also say that time travel is the much less likely scenario, since to our knowledge time doesn't actually exist as some kind of dimension you can travel but is only a kind of statistical property of the universe. You can change the speed with which time passes for you, but no going backwards.
FTL might not be impossible though, as mentioned above, if the theory of relativity is wrong it could certainly be possible, or maybe causality can be violated after all.
Anyway, time travel stories are very common in SF, just to add another obscure(ish) one to the mix, there is one book from Hohlbein (german author) i remember reading years back that included time travel. Actually the main characters future selfs coming back in time to get themselves as children and show them a future which they are then supposed to prevent. Or some such if i remember correctly, which i might not since i don't even recall the title.
Another time travel story i read more recently was by neal asher. Don't recall that title either, my bookshelf's at home and i'm not.
I'm pretty sure a search at amazon will turn up tons of time travel stories, though i can't think of any more. Not surprising, i'm terribly bad at suspension of disbelief, which makes time travel kinda annoying to read about since it's almost never thought out well enough to at least avoid the most glaring paradoxa. (seven days for example is awful in that regard)
As for a time traveller's artifact being seen as alien, the only story i can think of is Sphere, though there might be others.