First Solution: Put $s_n = a_1 + \cdots + a_n = b_1 + \cdots + b_n$. Then
$$\begin{aligned} 2 \sum_{i=1}^{n-1} (a_1 + \cdots + a_i) &= 2(n-1)a_1 + 2(n-2)a_2 + \cdots + 2(1)a_{n-1} \\ &= (n-1)a_1 + (n-3)a_2 + \cdots + (1-n)a_n + (n-1)s_n \\ &= (n-1)s_n + \sum_{1 \le i < j \le n} (a_i - a_j) \end{aligned}$$
and similarly
$$2 \sum_{i=1}^{n-1} (b_1 + \cdots + b_i) = (n-1)s_n + \sum_{1 \le k < \ell \le n} (b_k - b_\ell).$$
By (*), these two quantities are equal, so
$$2 \sum_{i=1}^{n-1} (a_1 + \cdots + a_i) = 2 \sum_{i=1}^{n-1} (b_1 + \cdots + b_i).$$
Consequently, each of the inequalities $a_1 + \cdots + a_i \le b_1 + \cdots + b_i$ for $i = 1, \dots, n-1$ must be an equality. Since we also have equality for $i = n$ by assumption, we deduce that $a_i = b_i$ for $i = 1, \dots, n$, as desired.

Second Solution: Expanding both sides of (**) yields
$$(n-1) \sum_{i=1}^{n} a_i^2 + 2 \sum_{1 \le i < j \le n} a_i a_j = (n-1) \sum_{i=1}^{n} b_i^2 + 2 \sum_{1 \le k < \ell \le n} b_k b_\ell.$$
Squaring both sides of the given equation $a_1 + \cdots + a_n = b_1 + \cdots + b_n$ gives
$$\sum_{i=1}^{n} a_i^2 + 2 \sum_{1 \le i < j \le n} a_i a_j = \sum_{i=1}^{n} b_i^2 + 2 \sum_{1 \le k < \ell \le n} b_k b_\ell.$$
From the above relations we easily deduce that
$$\sum_{i=1}^{n} a_i^2 = \sum_{i=1}^{n} b_i^2.$$
By the Cauchy-Schwarz inequality, we obtain that
$$\left(\sum_{i=1}^{n} b_i^2\right)^2 = \left(\sum_{i=1}^{n} a_i^2\right) \left(\sum_{i=1}^{n} b_i^2\right) \ge \left(\sum_{i=1}^{n} a_i b_i\right)^2$$
or
$$\sum_{i=1}^{n} b_i^2 \geq \left| \sum_{i=1}^{n} a_i b_i \right| \geq \sum_{i=1}^{n} a_i b_i. \qquad (\dagger)$$
We set $s_i = a_1 + \dots + a_i$ and $t_i = b_1 + \dots + b_i$ for every $1 \le i \le n$. By Abel's summation formula, we have
$$\begin{aligned} \sum_{i=1}^{n} a_i b_i &= s_1 b_1 + [s_2 - s_1] b_2 + [s_3 - s_2] b_3 + \dots + [s_n - s_{n-1}] b_n \\ &= s_1(b_1 - b_2) + s_2(b_2 - b_3) + \dots + s_{n-1}(b_{n-1} - b_n) + s_n b_n. \end{aligned}$$
By the given conditions, $s_i \le t_i$ and $b_i - b_{i+1} \le 0$ for every $1 \le i \le n-1$ and $s_n = t_n$. It follows that
$$\begin{aligned} \sum_{i=1}^{n} a_i b_i &\ge t_1(b_1 - b_2) + t_2(b_2 - b_3) + \dots + t_{n-1}(b_{n-1} - b_n) + t_n b_n \\ &= t_1 b_1 + [t_2 - t_1] b_2 + [t_3 - t_2] b_3 + \dots + [t_n - t_{n-1}] b_n = \sum_{i=1}^{n} b_i^2. \end{aligned}$$
Combining the last inequality and $(\dagger),$ we conclude that the equality case holds for every inequality we discussed above. In particular, $s_i = t_i$ for $i = 1, \dots, n$. These inequalities immediately give us $a_n = b_n$, $a_{n-1} = b_{n-1}$, $\dots$, $a_1 = b_1$ and the problem is solved.

Third Solution: If $u = (u_1, u_2, \dots, u_n)$ and $v = (v_1, v_2, \dots, v_n)$ are two nonincreasing sequences, we say that $u$ majorizes $v$ if $u_1 + \dots + u_n = v_1 + \dots + v_n$ and $u_1 + \dots + u_i \ge v_1 + \dots + v_i$ for $i = 1, 2, \dots, n-1$. It is not difficult to see that $(a_n, \dots, a_1)$ majorizes $(b_n, \dots, b_1)$. By a theorem of Birkhoff, it follows that there are constants $c_\sigma \in (0, 1]$, where $\sigma$ runs over some set $S$ of permutations of $\{1, \dots, n\}$, with $\sum_{\sigma \in S} c_\sigma = 1$ and
$$\sum_{\sigma \in S} c_{\sigma} a_{\sigma(i)} = b_i \quad \text{for } i = 1, 2, \dots, n.$$
We will prove the inequality
$$\sum_{i,j=1}^{n} |a_i - a_j| \ge \sum_{i,j=1}^{n} |b_i - b_j|,$$
with equality if and only if $a_i = b_i$ for $i = 1, \dots, n$. With this result, we complete our proof by noting (***).
We have
$$\begin{aligned} \sum_{i,j=1}^{n} |a_i - a_j| &= \sum_{\sigma \in S} c_{\sigma} \sum_{i,j=1}^{n} |a_i - a_j| = \sum_{\sigma \in S} c_{\sigma} \sum_{i,j=1}^{n} |a_{\sigma(i)} - a_{\sigma(j)}| \\ &= \sum_{i,j=1}^{n} \sum_{\sigma \in S} c_{\sigma} |a_{\sigma(i)} - a_{\sigma(j)}| \ge \sum_{i,j=1}^{n} \left| \sum_{\sigma \in S} c_{\sigma} (a_{\sigma(i)} - a_{\sigma(j)}) \right| = \sum_{i,j=1}^{n} |b_i - b_j|, \end{aligned}$$
using the fact that $|x_1| + \dots + |x_m| \ge |x_1| + \dots + |x_m|$ for all real numbers $x_1, \dots, x_m$.
This establishes the desired inequality; it remains to check the equality condition. For this, we must have
$$\sum_{\sigma \in S} c_{\sigma} |a_{\sigma(i)} - a_{\sigma(j)}| = \left| \sum_{\sigma \in S} c_{\sigma} (a_{\sigma(i)} - a_{\sigma(j)}) \right|$$
for each pair $i$ and $j$; in particular, for each pair $i$ and $j$, the sign of $a_{\sigma(i)} - a_{\sigma(j)}$ must be the same for all $\sigma \in S$ for which $a_{\sigma(i)} \neq a_{\sigma(j)}$. It follows by the lemma below that the sequence $a_{\sigma(1)}, \dots, a_{\sigma(n)}$ itself must be the same for all $\sigma \in S$, yielding $a_i = b_i$.