I don't know if Monty hall problem counts as a paradox, but that is quite high on my favourite list of counterintuitive probability results.

In my experience the only reason the Monty Hall problem comes off as paradoxical is because it is usually poorly explained.

There is a 98.75% chance of some match of birthdays of the users who upvoted this post (57 at this moment)

For me it's Simpson's paradox: it throws everyone off -- it's caused (and will continue to cause) real-world damage, it's everywhere once you see it -- it's in how newspapers report science, it's in our social policy and how we talk about social issues, it's in court cases --, and finally, it's really hard to explain to a non-math person; so even when it's happening, you sound like the irrational one for pointing it out.

... and don't get cocky once you know about it, because it's so pernicious it'll get you too if you're not careful!

I do not think this is a particularly difficult concept to explain to anyone. A typical example (not difficult to find) and a simple graph are usually good enough for most people.