And on the pedestal these words appear:
'My name is Ozymandias, king of kings:
Look on my works, ye Mighty, and despair!'
Nothing beside remains.
The issue that I struggle with here is the stability over time..I get the feeling it'd be easier to find it in mathematics or something to that extent, but by the way you've written the question, it almost seems like you're wanting people to look out a spaceship window and see it. When it comes to it, anything that exists on a planetary scale is eventually going to be reorganized by gravity as you extend the time line into the billions of years.
Art is ultimately beauty in the eye of the beholder. I've seen mention that a dog differentiates smells. They will smell peas, carrots, potatoes, meats, water, flour, and butters...we smell the full stew (can a dog appreciate the stew?). In artwork, you can stare at the individual brushstrokes, or you can appreciate the full painting. Following these lines, perhaps a series of spinning nuetron stars that produce background xray radiation thats relatively meaningless on its own becomes a song when listened to together. Though thats hard as over a billion year time scale, these eventually rearrange...but song left in background radiation that can only be heard/appreciated when taken as a symphony not individual 'sounds' would be one way of leaving this timeless.
Perhaps it can be found in the really massive...2 super massive black holes oribiting each other in a binary method at the center of the universe who's combined momentum is truly 0 for eternity. Perfection is a way of conveying intelligence afterall, however it's easy for any of this not to be interpreted correctly.
Perhaps it can be found as a hidden message in time...In the Planck epoch of the big bang (between 0 and 10^-43 seconds), the particles suddenly rearrange to flip us off.
Maybe we've seen it just haven't care to notice it. 1-8-1, the configuration of protons in water, is their symbol for joy?
Or we can get to silly…A higgs boson particle has a smiley face drawn on it?
Edit:
If you are looking for something a ship could accidentally stumble upon, it would be (theoretically) possible to have a location where the interference of background radiation with itself produces a 'song' to be heard. A single pinpoint (or reoccurring pinpoints) where background radiation from all directions uniquely combines to create something in it's interference...gives it something that cannot be found in the parts, only in the appreciated whole (which is a common place within art). Would definitely give that awe and disbelief feeling you are looking for, whether or not they attribute it to that race of ascending beings is hard to tell...and probably quite disputable.
Starting to feel like a 'proof of the existance of god' style question...everywhere yet no where.