Paper is a good one but the media is low-density and fragile. Although pre-industrial forms of paper (e.g. cotton paper, or papyrus) might have more long-term resistance than modern wood paper.
Fired clay tablets are much more resistant, but lower density (because clay), unless you use a dedicated press maybe (most of the ancient Near East clay tablets were actually fired fortuitously e.g. by a building burning down, that was only rarely intended and most tablets were used as erase-boards). But obviously non-tablet pottery can go through millennia in rather good conditions.
Carved wood is also a good idea, but it still needs good conditions and maintenance. Still, in the right storage it can last for centuries (see the Tripitaka Koreana for instance).
Leather, parchment, and vellum too, but I think then your main concern will be the degradation of the pigments.
If your focus is on longevity above all else, then you can’t beat stone. Though that can still be destroyed. I guess above stone would be highly non-reactive metals, however you’d need a metal which is not very precious as well (e.g. not gold, or silver, or platinum). I’m not very versed into metals and metallurgy, but I’d look towards titanium (it’s extremely reactive but not at normal temperatures), or bronze.
At one point there were disks made out of glass (versus the conventional polycarbonate), in theory that gives them infinite lifetime short of being physically destroyed. Though it does assume a compatible drive device.