An idea I've seen is including messages at several levels. At the outermost level you describe in very basic format how to build a magnifying glass. From there you have diagrams that are legible that describes how to build a microscope. From there you have more than enough space to describe the basics of what else is in there and to start describing your language. I'm thinking optical storage in a clear rock of some sort, as has already been prototyped.

If you assume motivated readers and human-level intelligence, you could end up with good results. It might take a decade or three, and a lot of mental firepower, but they could get there.

(The outer layer is the hardest, since our information density is lowest. Our "description of how to build a magnifying glass" might cover just the basic optics of curved glass and a very basic description of how to get to glass and how to curve it correctly, leaving a lot of the details up to the finder. After all, we did it without help. We're not so much trying to solve this problem for the finder as help them on their way.)

So, before jumping in to argue, remember I'm stipulating decades of dedicated effort by presumably an interested consortium of... whatever they are. I think we can safely stipulate an amount of effort at least as large as our society has dedicated to, say, Linear A and B, or the Voynich manuscript. I'm not trying to spec "Ugh wanders out of the jungle, sees our pretty rock, and personally has a 20th century civilization up and running in 10 years" or anything crazy.