From the top of my head:

Client -> Relay: ["PUSH", ] / ["PULL", ]

That with event kinds specific for this, probably in the 2k/3k range? Something that doesn't stick around forever, but can be deleted when someone comes to PULL the queue after someone has PUSHed into it.

It'd be an interesting concept to explore.