If I pick a random rearrangement (in an equally likely manner) of RIVENDELL, what is the probabiltiy that it will start with R? If I pick a random rearrangement (in an equally likely manner) of RIVENDELL, what is the probability that it will start with R?
The probability that I pick R is 1/9, but there are repetitions of other letters, so the probability that I pick those letters (E and L) are higher. How do I account for this?

You don't need to.
Imagine two ways to rearrange the letters:
If you shuffle "real" letters (from Scrabble, for example), then you don't need to take repetitions into account, since your letter R is unique (just suppose you number your letters, in order to distinguish them).
If you take randomly a word from all possible distinct word, then you need to take repetitions into account. But...
The difference between the two methods above? For instance, the word $RIVENDELL$, which is unique in the latter list, could appear four times with the former method, as $RIVE_1NDE_2L_1L_2$, $RIVE_1NDE_2L_2L_1$, $RIVE_2NDE_1L_1L_2$ and $RIVE_2NDE_1L_2L_1$. But this is true for any word: every one can appear from 4 "distinct" arrangements of numbered letters. Hence their relative frequency is the same, and your probability is $1/9$ in both cases.
Incidentally, you are right, the probability to get an E or an L as first letter is higher: it's simply 2/9 for each.
