It can probably be done by looking at the sum of squares of sizes of color clusters and then constructing an appropriate martingale. But here's a somewhat elegant solution: reverse the time!
Let's formulate the question like that. Let $F$ be the set of functions from $\{1,\ldots,n\}$ to $\{1,\ldots,n\}$ that are almost identity, i.e., $f(i)=i$ except for a single value $j$. Then if $f_t$ is a sequence of i.i.d. uniformly from $F$, and
$$g_t=f_1 \circ f_2 \circ \ldots \circ f_t$$
then you can define $\tau= \min \{ t | g_t \verb"is constant"\}$. The question is then to calculate $\mathbb{E}(\tau)$.
Now, one can also define the sequence
$$h_t=f_t \circ f_{t-1} \circ \ldots \circ f_1$$
That is, the difference is that while $g_{t+1}=g_t \circ f_{t+1}$, here we have $h_{t+1}=f_{t+1} \circ h_t$. This is the time reversal of the original process.
Obviously, $h_t$ and $g_t$ have the same distribution so
$$\mathbb{P}(h_t \verb"is constant")=\mathbb{P}(g_t \verb"is constant")$$
and so if we define $\sigma=\min \{ t | h_t \verb"is constant"\}$ then $\sigma$ and $\tau$ have the same distribution and in particular the same expectation.
Now calculating the expectation of $\sigma$ is straightforward: if the range of $h_t$ has $k$ distinct values, then with probability $k(k-1)/n(n-1)$ this number decreases by 1 and otherwise it stays the same. Hence $\sigma$ is the sum of geometric distributions with parameters $k(k-1)/n(n-1)$ and its expectation is
$$\mathbb{E}(\sigma)=\sum_{k=2}^n \frac{n(n-1)}{k(k-1)}= n(n-1)\sum_{k=2}^n \frac1{k-1} - \frac1{k} = n(n-1)(1-\frac1{n}) = (n-1)^2 .$$
Ori Gurel-Gurevich pointed out that the transitions under Rule 1 are like the Hamming distances from $\vec{0}$ in a random walk on a hypercube $C$ (the Ehrenfest urn model). Further, the average number of steps for a random walk to return to a vertex in a regular connected graph is the number of vertices. We can use this idea on the quotient by the antipodal map to get that the average return time on $C/\sim$ is $2^{n-1}$, so on the hypercube, the average time before you either return to $00\ldots0$ or hit its antipode $11\ldots 1$ is $2^{n-1}$. The first step from $00\ldots0$ moves to a state with a single $1$ and $n-1$ $0$s, so the average time to reach either $(n,0)$ or $(0,n)$ from $(1,n-1)$ is $2^{n-1}-1$.
On the way to becoming a uniform color, the balls have to pass through a state with a single ball of one color, and $n-1$ of a second color. So, $2^{n-1}-1$ is an exponential lower bound for the expected number of steps from the original position with $n$ colors.
Here is a simple way to get an exponential upper bound for Rule 1. First, pick a color with $1$ element, and consider the probability that the next $n-1$ steps each increase the size of that color. This is at least $$p= \frac{n-1}{n}\frac{1}{n-1} \times \frac{n-2}{n}\frac{2}{n-1} \times ... \frac{1}{n}\frac{n-1}{n-1}= \frac{(n-1)!^2}{ n^{n-1}(n-1)^{n-1}}. $$
By Stirling's formula, $(n-1)! \sim \sqrt{2\pi (n-1)} ((n-1)/e)^{n-1}$ so
$$p \sim \frac{2\pi (n-1)^n}{n^{n-1} e^{2(n-1)}} \sim \frac{cn}{e^{2n}}.$$
The probability is even greater if you pick a color with more than one element, since you get the first few steps for free. Because the probability that the process will end in the next $n$ steps is at least $cn/(e^{2n})$, the expected number of steps until completion is at most $O(e^{2n})$.
Part of Johan Wästlund's answer to part 1 can be turned into bounds for Rule 2. Consider the number of pairs of balls which don't have the same color. This starts at $n \choose 2$. At each step, you choose an ordered pair of balls $(a,b)$. Conditioned on the choice of the unordered pair $\lbrace a, b \rbrace$, the expected number of pairs of balls of different colors decreases by at least $1$:
Suppose there are $c_a$ balls of the same color as $a$, and $c_b$ balls of the same color as $b$. The conditional probability that the ordering is $(a,b)$ is $(n-c_b)/(2n-c_a-c_b)$. The number of pairs of balls of different colors is decreased by $1 + c_a - c_b$. Conditioned on the event that the unordered pair was $\lbrace a, b\rbrace$, the number of pairs of balls of different colors is decreased on average by $1 + \frac{(c_a-c_b)^2}{2n-c_a-c_b} \ge 1.$
So, the expected number of steps under Rule 2 before all balls have the same color is at most $n \choose 2$.
This argument can be adjusted to give lower bounds which are better than linear. For $n \le x \le n^2/8$, if there are $x$ pairs of balls of the same color, then it takes an average of at least $k n$ steps for the number of pairs of balls of the same color to double to $2x$ for some constant $k$, since we can bound the numerator and denominator of $\frac{(c_a-c_b)^2}{2n-c_a-c_b}$ in terms of $x$. It takes about $\log_2 n - 2$ doublings to go from $n$ pairs the same color to $n^2/4$. This gives a lower bound of $\Omega(n \log n)$.
Here is an improved lower bound for rule 2. Suppose the number of ordered pairs of balls of the same color is $X \lt n^2/4$. $X = \sum_i c_i^2$ where $c_i$ is the number of balls of the $i$th color. We can estimate the expected change $E\bigg[2 + \frac{2(c_a-c_b)^2}{2n - c_a - c_b}\bigg] \le 2 + \frac{k}{n}E[c^2]$ where $k$ is some constant, and $c$ is the number of balls of the color of a random ball. $E[c^2] = \frac{1}{n} \sum_i c_i^3 \le \frac{1}{n} (\sum_i c_i^2)^{3/2} = \frac{1}{n}X^{3/2}$. (The inequality is that the $L^3$ norm is smaller than the $L^2$ norm.)
The number of ordered pairs of balls of the same color increases by at most $2 + \frac{k}{n^2}X^{3/2}$ per step on average. $X$ starts at $n$, and when $X \lt n^{4/3}$, the number of ordered pairs of balls of the same color increases by at most $2+k$ on average, so the expected number of steps for $X$ to reach $n^{4/3}$ (en route to $n^2$) is $\Omega (n^{4/3})$.
I believe that applying this up to $n^2$ would only give another factor of $\log n$, so this is still a bit off of the empirical result of about $n^{3/2}$.
Best Answer
I think you can verify Greg Martin's answer using indicator variables and linearity of expectation.
Let the random variable $X_i$ be the number of steps where one of the balls has the $i$th color before the $i$th color either disappears or becomes the only color.
The expected value of $X_i$ is as in the Gambler's Ruin, that is, $1 \cdot (n-1) = n-1$.
Each step involves two colors, hence the time to a single color is $\frac{1}{2} \sum X_i$.
The $\binom{n}{2}$ answer follows.