The lunar hardware will last quite a while, but it's still small and fragile on a timescale of billions vs a few million years.

So, I propose we do the following:

Using a few thousand excess thermonuclear weapons, we etch a huge logo into the moon.

Let's say you use 1 megaton bombs, which produce craters a km or so across, to write out "EARTH WAS HERE" in letters 25 km high. Put bombs a km or so apart and excavate deep, straight trenches. Add up the lines and it should take about 2,000 warheads. Scratch it out one of the youngest, flattest mare surfaces you can find.

Given current impact rates, that feature should remain visible and be clearly non-natural until the Sun turns into a red giant.

Better yet if you're serious about this, intead of a cute phrase make it a geometrically simpler shape, like a perfect square with a circle in it or something, then repeat it two or three times in widely spaced locations to guard against the possibility of having another Tycho-sized impact that just happens to be centered on your lovely little drawing.