My rough-and-ready suggestion before was that a paradox is a puzzle of some kind. But what kind? Not all puzzles are paradoxes, after all. There is nothing particularly paradoxical about standard jigsaw puzzle. Even those frustrating little metal puzzles aren't paradoxical — even if we can't figure out how to solve them. One might suggest that a paradox is a linguistic puzzle something that has to be stated in words — a "riddle", perhaps. This apparently rules out M.C. Escher drawings as paradoxes, but let that go for the moment. It still seems too permissive a definition. Crossword puzzles are linguistic puzzles; but again, even if they can be frustrating (especially on Sundays), they do not seem especially paradoxical.
We might cross the puzzle suggestion with the surprising suggestion from before and say that a paradox is a surprising puzzle or riddle. This raises an interesting connection and a further question: can paradoxes be simply questions? This would run against the grain in philosophy of understanding paradoxes as sets of propositions with a certain character. But consider Zen Koans. The OED defines them as "A paradox put to a student to stimulate his mind." As I understand Koans (and I'm a bit out of my depth here), they are often presented as questions. The most famous is, of course, "What is the sound of one hand clapping?" On the other hand, you might have heard demonstrations of the straightforwardness of this puzzle. For example, there's this guy:
Perhaps he's not ready to have his mind stimulated. . . . Perhaps the question isn't too deep after all. Here's another one: "Could there be a barber who shaves all and only those who do not shave themselves?"