My apologies if this is too elementary, but it's been years since I heard of this paradox and I've never heard a satisfactory explanation.  I've already tried it on my fair share of math Ph.D.'s, and some of them postulate that something deep is going on.

The Problem:

You are on a game show.  The host has chosen two (integral and distinct) numbers and has hidden them behind doors A and B.  He allows you to open one of the doors, thus revealing one of the numbers.  Then, he asks you: is the number behind the other door bigger or smaller than the number you have revealed?  Your task is to answer this question correctly with probability strictly greater than one half.

The Solution:

Before opening any doors, you choose a number $r$ at random using any continuous probability distribution of your choice.  To simplify the analysis, you repeat until $r$ is non-integral.  Then you open either door (choosing uniformly at random) to reveal a number $x$.  If $r < x$, then you guess that the hidden number $y$ is also smaller than $x$; otherwise you guess that $y$ is greater than $x$.

Why is this a winning strategy?  There are three cases:

1) $r$ is less than $x$ and $y$.  In this case, you guess "smaller" and win the game if $x > y$.  Because variables $x$ and $y$ were assigned to the hidden numbers uniformly at random, $P(x > y) = 1/2$.  Thus, in this case you win with probability one half.

2) $r$ is greater than $x$ and $y$.  By a symmetric argument to (1), you guess "larger" and win with probability one half.

3) $r$ is between $x$ and $y$.  In this case, you guess "larger" if $x < y$ and "smaller" if $x > y$ -- that is, you always win the game.

Case 3 occurs with a finite non-zero probability $\epsilon$, equivalent to the integral of your probability distribution between $x$ and $y$.  Averaging over all the cases, your chance of winning is $(1+\epsilon)/2$, which is strictly greater than half.

The Paradox:

Given that the original numbers were chosen "arbitrarily" (i.e., without using any given distribution), it seems impossible to know anything about the relation between one number and the other.  Yet, the proof seems sound.  I have some thoughts as to the culprit, but nothing completely satisfying.

Insightful members, could you please help me out with this one?  Thanks!

After Bill's latest clarifications in the commentary on Critch's answer, I think the question is interesting again. My take:
One thing that always seemed to fall through the cracks when I learned about probability theory is that probability is intricately tied to information, and probabilities are only defined in the context of information. Probabilities aren't absolute; two people who have different information about an event may well disagree on its probability, even if both are perfectly rational. Similarly, if you get new information relevant to a certain event, then you should probably reevaluate what you think is the probability that it will occur. Your particular problem is interesting because the new information you get isn't enough for you to revise that probability by purely mathematical considerations, but I'll get to that in good time.
With the previous paragraph in mind, let's compare two games:
G1. You are given two closed doors, A and B, with two numbers behind them, and your goal is to choose the door with the higher number. You are given no information about the doors or numbers.
G2. You are given two closed doors, A and B, with two numbers behind them, and your goal is to choose the door with the higher number. You are allowed to look behind one of the doors and then make your choice. 
For the first game, by symmetry, you clearly can't do better than choosing a door randomly, which gives you a success probability of exactly 1/2. However, the second game has a chance of being better. You are playing for the same goal with strictly more information, so you might expect to be able to do somewhat better. [I had originally said that it was obviously better, but now I'm not so sure that it's obvious.] The tricky thing is quantifying how much better, since it's not clear how to reason about the relationship between two numbers if you know one of the numbers and have no information about the other one. Indeed, it isn't even possible to quantify it mathematically.
"But how can that be?" you may ask. "This is a mathematical problem, so how can the solution not be mathematically definable?" There's the rub: part of the issue is that the problem isn't formulated in a mathematically rigorous way. That can be fixed in multiple ways, and any way we choose will make the paradox evaporate. The problem is that we're asked to reason about "the probability of answering the question correctly," but it's not clear what context that probability should be computed in. (Remember: probabilities aren't absolute.) In common probability theory problems and puzzles, this isn't an issue because there is usually an unambiguous "most general applicable context": we should obviously assume exactly what's given in the problem and nothing else. We can't do that here because the most general context, in which we assume nothing about how the numbers $x$ and $y$ are chosen, does not define a probability space at all and thus the "probability of answering the question correctly" is not a meaningful concept.
Here's a simpler ostensible probability question that exhibits the same fallacy: "what's the probability that a positive integer is greater than 1,000,000?" In order to answer that, we have to pick a probability distribution on the positive integers; the question is meaningless without specifying that.
As I said, there are multiple ways to fix this. Here are a couple:
I1. (Tyler's interpretation.) We really want the probability of answering the question correctly given a particular $x$ and $y$ to be greater than 1/2. (The exact probability will of course depend on the two numbers.)
I2. (Critch's interpretation.) More generally, we want the probability of answering correctly given a particular probability distribution for $(x,y)$ to be greater than 1/2. (The exact probability will of course depend on the distribution.)
(Those two are actually equivalent mathematically.) Clearly, if we knew what that distribution was, we could cook up strategies to get a success probability strictly above 1/2. That's pretty much obvious. It is not nearly as obvious that a single strategy (such as the one in the statement of the question) can work for all distributions of $(x,y)$, but it's true, as Bill's proof shows. It's an interesting fact, but hardly paradoxical now.
Let me summarize by giving proper mathematical interpretations of the informal statement "there is a strategy that answers the question correctly with probability strictly greater than 1/2," with quantifiers in place:

(1a) $\exists \text{ strategy } S: \forall x, y: \exists \delta > 0$: $S$ answers correctly on $x$, $y$ with probability at least $1/2 + \delta$.
(1b) $\exists \text{ strategy } S: \forall \text{ probability distributions } P  \text{ on } \mathbb{N}^2: \exists \delta > 0$: $S$ answers correctly, when $x$, $y$ are chosen according to $P$, with probability at least $1/2 + \delta$.

I think with the proper quantifiers and the dependence on $x$ and $y$ explicit, it becomes a cool mathematical result rather than a paradox. Actually, based on my arguments at the beginning, it's not even that surprising: we should expect to do better than random guessing, since we are given information. However, simply knowing one number doesn't seem very useful in determining whether the other number is bigger, and that's reflected in the fact that we can't improve our probability by any fixed positive amount without more context.
Edit: It occurred to me that the last part of my discussion above has a nonstandard-analytical flavor. In fact, using the first version of the formula for simplicity (the two being equivalent), and the principle of idealisation, I think we immediately obtain:

(2) $\exists \text{ strategy } S: \exists \delta > 0: \forall \text{ standard }x, y:$ $S$ answers correctly on $x$, $y$ with probability at least $1/2 + \delta$.

(Please correct me if I'm wrong.)
The number $\delta$ is not necessarily standard, and a basic argument shows that it must actually be smaller than all standard positive reals, i. e., infinitesimal. Thus, we can say that being able to look behind one door gives us an unquantifiably small, infinitesimal edge over random guessing. That actually meshes pretty well with my intuition! (It might still a nontrivial observation that the strategy $S$ can be taken standard; I'm not sure about that...)
