How can one encrypt with RSA (or ElGamal) without revealing whom the ciphertext is intended for? Imagine Alice wants to encrypt for Bob and post this encryption publicly, so that only Bob can decrypt but no one can other than Alice or Bob tell that the message was encrypted for Bob.

The naive approach leaks some information.  If Alice posts $y = x^e \bmod{n}$, then an observer can conclude that the recipient has a public key $n &gt; y$, and can therefore eliminate many guesses as to whom the recipient is. Potentially this advantage can be amplified, depending on the higher-level protocol.

My thought was Alice can generate a random $r$ of size $2^{\textrm{L}}$, where $L$ is the largest allowable key size, and post $y + rn$.  Then, Bob can consider the residue mod $n$ when decrypting.

Similarly, in ElGamal, Alice can pick random $r_1$ and $r_2$, then post $\langle c_1 + r_1 p, c_2 + r_2 p \rangle$.

Do these constructions achieve their intended goals?

A use case for this is in PGP encryption.  Assuming Alice strips the key id from the outer packet, can she post a PGP encryption without leaking information about her intended recipient?
Your aim is to have a number $y' = y + rn$ that gives an uniform distribution over any valid key modulus $n'$, so that no keys can be ruled out. For that, you need $y'$ to be uniformly distributed modulo a larger number. How large is the question.

If you have uniform samples from $[0, 2^l-1]$, according to this (pdf, page 20 talking about key generation, but should apply here) they are uniform (enough) modulo $n &lt; 2^k$ if $l = k + 64$. Hence, to have your $y'$ be uniform for keys up to $L$ bits you should draw $y'$ from $[0, 2^{L+64}-1]$.

Your approach gives even larger numbers ($2^{L+lg(n)} &gt; 2^{L-lg(n)+64}$ with a realistic $n$), so that part's covered, but it may leak the minimum size of $n$, since if $r = 2^L$, no key with $n'&lt;n$ could result in so high a number $y'$.

You should instead draw $r$ from $[0, 2^{L-lg(n)+64}-1]$, rounding the exponent so that $y'$ can reach $2^{L+64}-1$, then throw away those $r$ values that give you $y' &gt; 2^{L+64}-1$.

(You could find a better upper bound for that random number generation, but generating uniform random numbers that aren't modulo a power of two is itself tricky. At worst you'll be throwing away half the $r$ values, so that should be easy enough.)