Best bet I can think of would be to mass produce something that ~doesn't decompose and spread a bunch everywhere so at least one will be found.
Something like diamond plaques with writing on them, maybe just reuse what we put on Voyager but in different materials.
I bet there's a better material than diamond, not sure what though. You'd want something that lasts, but not something that can be reused. Eg don't use gold, someone will melt it down later...
Enormous piles of very skillfully worked massive stone blocks. Artifacts made of common, long-lived matter so precisely crafted that we could barely duplicate them today.
You mean like pyramids? Heh look at what few thousands of years caused to them, and its not even very challenging environment (very low humidity, mostly sand abrasion). In fact, go to mountains and actually try to look around a bit from geological perspective - they are constantly being weathered, all types of rock, by mostly rain and elements. Elements cut through stone like through butter.
Just because something doesn't visibly keep disappearing in front of your eyes doesn't mean its some ultra stable form to last for a billion years.
Also, one proper earthquake and your fine stone structure is a big pile of rubble. Now do it 100x.
From a geological perspective, several types of rock will last more than long enough. Maybe you're thinking too long-term, heh.
During the last 2.6M years - and man's been around -at least- that long - there've been a dozen or two ice-ages. Between them were interglacials, some of which lasted 2 or 3 times longer than our 10,000-year holocene. More than enough time and resources for an earlier (even wiser or saner) humanity. Or three.
Or we could mark the Earth-facing side of the Moon somehow; that would endure over geological time scales. Maybe not via massive excavations with nuclear charges (sounds like vandalism to me), but, say, hundreds of kilometers long figures/patterns made with aluminium foil sheets hung on poles, or just spread on the regolith (so - easily removable).
Stone blocks will be quarried, weathered, ground by glaciers and then subducted beneath the crust. Small artifacts disappear even faster and are harder to find.
Maybe to drive this point home from another point of view: the dinosaurs roamed the earth for tens of millions of years. We have so little evidence from that, that our ideas what they looked like have changed significantly from the portrayal in Jurassic Park.
Humans have been around for a frw hundred thousand years (if you're generous). Our current traces will be gone in a few million.
Something like diamond plaques with writing on them, maybe just reuse what we put on Voyager but in different materials.
I bet there's a better material than diamond, not sure what though. You'd want something that lasts, but not something that can be reused. Eg don't use gold, someone will melt it down later...