This, then, is the ultimate paradox of thought: to want to discover something that thought itself cannot think. -Søren Kierkegaard
Paradoxes are mental mysteries that lead us to impossible places. Trying to puzzle out a paradox through logic is a bit like pacing the floor and suddenly finding yourself on the ceiling. Paradoxes often help us understand important philosophical concepts, because trying to resolve them causes us to think deeply about subjects like language, free will and infinity. Others are simply unexpected results that expose errors in the assumptions that we humans tend to make. Some would say the latter are not true paradoxes, but that is only because we have figured them out. Paradoxes are related to cognitive illusions and fallacies, which can both be thought of as weak paradoxes.
One definition of a paradox is when apparently acceptable premises proceed by apparently acceptable reasoning to an apparently unacceptable conclusion. If we later determine that the conclusion is acceptable after all, or that one of the premises is in fact unacceptable, we may no longer consider the problem to be a paradox. In this spirit, Bertrand Russell advised logicians to collect paradoxes and use them as experiments to test logical theories.
A broader definition of a paradox is simply an unexpected or apparently contradictory result. Paradoxes are inherently appealing in part because of this quality of the unexpected, which they share with optical illusions, and with jokes.