Apparent Paradox in the Idea of Random Numbers This question is a bit less than rigorous, but it's only because I don't know how to formulate it rigorously.

Suppose there was some machine, or function, or whatever that could output a random positive whole number. Let's say that it has done its job and I have a number n. 

Here's what seems like a paradox to me: if n really was randomly generated, I shouldn't be surprised by its value, no matter how big or small. After all, there is no number that I should have expected more than any other.

On the other hand, if I asked the question of whether I expected the number to be bigger or smaller than the one that I got, the answer would always be bigger. In fact, it was infinitely more likely that I would have gotten a number bigger than what I got. If I got a digit with one billion digits, there are still infinitely more numbers above n than there are below it. No matter the number, it is infinitely improbable that it could have been that small.

Is it just that the idea of picking randomly from an infinite set doesn't make any sense? Or is this a problem that one also runs in to when trying to pick a random element of a finite set?
Picking a number at random from an infinite set makes perfect sense. It just can't be done uniformly over all points. You would have to specify the probability of (in your case, the natural numbers) choosing each and every natural number. That is, for every $n\ge 1$ you must specify a probability $p_n\ge 0$. The only requirement is that $\sum_np_n=1$. Now, your paradox arises from the hidden supposition that the distribution is uniform, i.e., that $p_n=p_m$ for all $n,m$. This is of course inconsistent, so no such probability distribution exists. 

Now that you know that, you must revise your question and see if the paradox survives. So, if you are now given a machine that generates a random natural number according to some distribution (which may or may not be known to you), are you surprised at the outcome? if you see the number $1005$, do you expect the next number to be larger or smaller?
I'm very rusty, but I'd say if you want the probability that a number is lower than your current pick, you'd use the following formula, where A = the maximum number in the set and B is the number you picked:

P(lower) = 1 - (A-(B-1))/A

So if you were picking from 1 to 10 and picked 9, the probability of picking a lower number would be 1 - (10-(9-1))/10, or 0.8.

How this works when A is infinite is a bit beyond me, but intuitively I'd agree with you: dividing infinity by infinity is 1 (except it isn't, but it feels right!), and then 1-1 is zero, so P(lower) will be 0.