Sometimes the simplest solution is the most compelling. The oldest surviving printed book is about 1150 years old. If we expand our search to all material printed on flexible organic fibers, we can double that easily -- the oldest papyrus is about 2700 years old. Keep in mind that these have had to survive unpredictable storage conditions and the vagaries of human beings, which your storage cache would presumably not be subject to.
Engraved or etched metal would probably be better but decidedly more expensive, time-consuming to write to, and bulkier to store. Some sort of metal-paper hybrid might be good to keep the size & weight comparable -- a metal foil, bonded to flexible fibers. The fiber backing would prevent tearing of the thin foil, and the foil would be more resistant to becoming brittle and crumbling.
Being able to read your media without obsolescence-prone technology is important. Microfilm is an excellent example of future-proof storage technology. While not a viable enough medium itself to serve as a solution for this problem
(silver-halide film "can last more than 500 years", but I'd be concerned about radiation exposure, and it requires temperature-controlled storage), all it will ever require to read is a magnifying element of some sort (anything from a fancy collection of electronics to a chunk of clear, shaped crystal) and a bright light. For a real-life case study, the Voyager record is a fascinating & well-known example of attempting to create a media storage object & accompanying instructions for playing it, intended for interpretation by an alien audience.
With all the radiation and generally extreme conditions found in space, I'm pretty concerned about the viability of human embryos at these timescales, so I'm going to take this a step further. Let's treat them as data and store them, too!
Now, it's easy to say that you can just store genomes on paper -- but is it really a workable solution? Assuming we have perfect copies of genomes, they're about 3 billion letters apiece. A very rough experiment (Verdana, 6pt, default margins, "gatc" repeated) gives ~13,000 characters per page => 230,000 pages. A typical box of printer paper is 10 reams (5000 sheets) -- so that's 46 boxes of paper for a single genome. Not great. This could of course be shrunk significantly by using an optimal typeface, minimal margins, double-sided printing, possible shorthand for letter pairs, etc. Still, that's a lot of paper, especially since you presumably want to store many embryos. However, there is a workaround! Only about 0.1% of our genome varies between individuals (ignoring rare variants). Thus, you can store a reference genome, and diffs for individuals. That brings us down to 230 pages per person -- only half a ream, even at my original, highly inefficient & inflated calculation.
To ensure sequence integrity, the genome could be encoded into binary and parity bits (or other error detection/correction techniques) could be applied to the data prior to printing -- but this would come at the cost of obfuscating the inherent readability of a plaintext genome. It'd certainly use a lot less paper, though.
However you encode it, be sure to number the pages! Or at least stripe the ends of them with a marker, punchcard-style.