Thank you all for your answers. Would aluminium foil Be a suitable substrate?
I might be worse than paper. It can rot away within a decade or two based on what I've seen in some cases, and it would be difficult to get a good bond between the aluminum and the emulsion. It's just too fragile. I'd be more inclined to use a stainless steel plate with some good thickness (1/8 inch, maybe). But I still think stone is the most feasible way to go, balancing cost with longevity.
"Truth and love are my law and worship. Form and conscience are my manifestation and guide. Nature and peace are my shelter and companions. Order is my attitude. Beauty and perfection are my attack."
Like Nicholas said, ceramic would be a pretty good bet. Gold.... always a good choice. Glass, I don't see why not. Some might even say that a high-grade plastic would be up the challenge, like polyethylene, and that could be rolled up.
But, is cyanotype really the longest lived photo artifact out there? Platinum/palladium might be better, or even carbon.
By the way, are you actually going to be putting this in a time capsule?? That's awesome...