Depending on you assess the progress of AI capabilities moving forward, reaching the goal of "provably computationally hard or impossible" may not achievable. Specifically I'm thinking of future AI that equals or exceeds capabilities where humans are currently considered more proficient than computers.
Anyway, I'd suggest a condition of "practically computationally hard or achievable currently (or likely in the future)".
To that end a complex painting with various subtle clues, letters, or words as an integral part of the work, could communicate a message (or a key to a cipher) that could be relatively easy for most humans (possibly of a given culture) to interpret, but very hard for an automaton. The clues would be best if they were novel (not something from an existing knowledge base). In effect kind of a super-rebus or modern day hieroglyphics.
Similarly, some sort of performance art, where the message is communicated non-verbally, or figuratively. For example, a speech, where the words themselves are not the message, but the intonation, implication, what's not spoken, etc. are the sort of things that convey the message.
Certainly anything that relies on shared, private history between the participants would be hard for anything/anyone without the shared history to interpret.
Finally any kind of medium that heavily used artistic symbolism, again novel, could be used.
As with any encryption scheme, the threat model should be considered. If you want to use your company's network to send private messages and don't want them flagged by virtue of a simple keyword search, (and aren't worried about humans scanning the messages flowing through the company network) then a pretty simple scheme could be used, such as a cartoon like rebus. But if your adversary was more formidable, then a video with an actor miming the message may be more appropriate.