So if I understand you correctly your real question is about textual transmission. What texts are most likely to survive from antiquity, and on what materials?

Frankly, very little text survives from antiquity at all. We have reason to believe that most of the texts that we have area pretty representative of the best stuff, but what actually survives is a tiny fraction of the literary output of the ancient world, which was simply gigantic. Of the literature that we have, with very few exceptions the manuscripts are medieval, not ancient. Papyrus and vellum do not last very well at all, and the reason we have most of these texts is because they were copied over and over again for centuries by monks and scribes, often long-forgotten by anyone outside of the particular monastery where the manuscript was housed. Of course, this applies to actual literature, not to random scraps of papyrus (although in A Canticle for Leibowitz, which is set after a nuclear holocaust, the author imagines the monks of the new illiterate age as zealously guarding every scrap of pre-nuclear paper). Nobody copied little letters left for some asshole to his girlfriend--the existence of letters from people like Cicero is purely due to the fact that those letters were collected and published as literary works. So we're reduced to the existence of the original papyrus or vellum, hoping that it gets preserved. In almost all cases it doesn't--only under specific environmental conditions can we have any hope of papyrus' survival, and even then it's mostly luck. The conditions of Africa and Egypt are nice for preserving papyrus, and the trash heap at Oxyrhynchus has yielded a huge quantity of papyrus scraps, much of it containing administrative notes, personal letters, etc. But those are very particular conditions, and even then most of the material did not survive or is so fragmentary or damaged as to be essentially worthless.

The largest source of real legibly text straight from antiquity and not copied later is of course epigraphy. There are hundreds of thousands inscriptions, some of them quite complete, others less so. Even then the proportion of inscriptions that have survived is really pretty small, and the ones that are actually legible or complete enough to tell us anything is even smaller. You mention the possibility of losing inscriptions in buildings--in fact, a lot of the time that preserves them. In Rome there are thousands of inscriptions plastered into the walls of old buildings, and if you go into rural towns it's even more common--I remember staring at the church bell tower at Capua and trying to figure out what the monumental inscription they had used as building material had originally said, since the builders had smashed it and repositioned the fragments so that they fit into gaps that needed filling. But inscriptions fail to survive for all kinds of reasons. They erode away, are destroyed deliberately or by some accident or disaster. If they're marble they might be burned for lime. And there are certainly thousands more inscriptions that we simply haven't found, because they're buried at a site that hasn't been excavated, or perhaps were placed along some road somewhere where they got buried--with nothing around why would anyone excavate there?). Sometimes they're just forgotten about--I remember I lucked out at Rome when I found an inscription I had been searching for in one of the catacombs and which nobody there could find, and happened to stumble across it in the very back of the gift shop, holding up a railing. Not quite a comparable case, as the inscription had been cataloged and moved there, but in the same way that manuscripts can be forgotten about in monasteries, only to turn up in some inventory hundreds of years later, inscriptions can also be in obvious places but totally forgotten. Greek inscriptions from the 5th Century are relatively rare, though--much of the reason for the abundance of Roman epigraphy is the so-called Epigraphic Habit, which resulted in a corresponding explosion of epigraphical material in the post-Augustan period. Epigraphy exists on other materials, though. We have gazillions of lead curse tablets from Athens alone, rolled up (and often pierced with a spike) and deposited in the ground, often in graves. A lot of these are pretty damaged, though, and there's no guaranteeing that any given one will survive in the ground--and they survive because they've been buried, above ground they would have been melted down just like a bronze inscription, of which we have precious few despite our knowledge that bronze was among the more common epigraphical media. If we were to presume the existence of our hypothetical time-traveler hoping to leave a message to some future age he's certainly more likely to succeed by using a more permanent, epigraphical medium than wood, paper, or wax, but there's no guarantee that his writing would survive (and less that it would survive intact) or that even if it did anyone would ever actually find it