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...
Plastics? Micro plastics?
Humans have been around for a frw hundred thousand years (if you're generous). Our current traces will be gone in a few million.
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.
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.
"Our historians say it is the genitalia of a species who lived in ancient times."
;)
Replace as many plants and animals as we can with genetically engineered versions that have messages encoded in their junk DNA.
That would not be good enough to tell aliens who visit long after all life on Earth has gone extinct that we were here, but could work for future intelligent species that evolve from existing Earth life after humanity is long gone.