**Edit:** I make the mistake below of proving a lower bound on the maximum number of boxes Alice must open, not the expected number. So this does not answer the question.

.

I think this sort of thing is often argued with [Yao's principle][1] (which is really just von Neumann's minimax):

 $$ \max_{\text{randomized algorithm}} \min_{\text{sequence}} \mathbf{E}[\text{performance}] \leq \min_{\text{distribution on sequences}} \max_{\text{deterministic algorithm}} \mathbf{E}[\text{performance}] .$$

It is a two-player game between Alice, who chooses the (randomized) algorithm, and Lucy, who chooses the input sequence. In this case $\mathbf{E}[$performance$]$ is the probability that Alice finds a red ball.

To apply it, we just need to upper-bound the right-hand side. We do that by, not actually taking the minimum over all possible distributions on sequences, but just finding one distribution on sequences that is bad for all deterministic algorithms that Alice could employ.

So here's the idea. First, suppose that an algorithm can only open $o(\log n)$ boxes. Now, if we just find a single distribution on input sequences such that every deterministic algorithm has $\Pr[$find red$] < 1-1/n$, then we are done: The minimum on the right-hand-side is certainly less than $1-1/n$, since we have found an example where it is less than $1-1/n$. Then Yao's principle says that any randomized strategy of Alice performs worse than $1-1/n$ on its worst-case input distribution. (That is, on the worst-case strategy of Lucy.)

So concretely, I think we can apply it here by letting Lucy choose the distribution of sending the boxes in uniformly random order. Then for any deterministic algorithm of Alice's that opens $k$ boxes, the probability that none are red is

 $$ \left(1-\frac{k}{2n}\right) \left(1-\frac{k}{2n-1}\right) \cdots \left(1-\frac{k}{n+1}\right) .  ~~~~~~~~~~~~~ (1) $$
Why is this? Fix the $k$ boxes Alice will open (remember we are only worried about deterministic Alices). Now imagine Lucy randomly choosing the locations of the red balls one by one. The first has $2n$ choices, so a probability $1-k/2n$ that is does not choose one of our $k$ boxes. The second has $2n-1$ choices, conditioned on the choice of the first, so a probability $1-k/(2n-1)$ that it does not choose one of our $k$ boxes. And so on for the $n$ red balls. The important thing is that we can't assume that each of the $k$ boxes independently has a red ball with probability $1/2$, since they aren't independent (if one box doesn't, the others are more likely to). I think you might make this mistake in your statement of the upper bound, but if so I'm sure it's easily fixed.

Anyway, I don't know immediately how to argue that (1) is at least $1/n$ when $k < o(\log n)$, but it should be true, since (1) is at least

 $$ \left(1-\frac{k}{n}\right)^n \approx e^{-k}.$$

(The approximation has the inequality going the wrong way, so we don't immediately get the proof.)

**Edit**. If there is anything unclear, please let me know. I probably did a poor job explaining, but this is a primary technique for lower bounds for online/randomized algorithms and I think it gives what you want pretty simply.

  [1]: http://en.wikipedia.org/wiki/Yao's_principle