Proof of Brillouin's theorem using the diagonality of the Fock matrix
Your question actually contains two linked inquiries. The proof itself depends on the nature of the Fock-operator to which I'll have a few words afterwards. For the proof itself it is only important, that the Fock matrix is diagonal. Let's restate Brillouin's theorem:

In case of the Hartree-Fock (HF) reference determinant $\Phi_0$, the Hamiltonian matrix element between it and any singly excited determinant $\Phi_a^r$ reduces to zero. 
$%
\newcommand{\ll}{\left\langle}\newcommand{\rr}{\right\rangle}
\newcommand{\lb}{\left|}\newcommand{\rb}{\right|}
\newcommand{\op}[1]{\mathbf{#1}}$
$$\langle\Phi_0|\op{H}_\mathrm{el}|\Phi_a^r\rangle = 0$$

The proof of this then rather simple:
\begin{align}
&amp;&amp; E &amp;= \ll \Phi_0 \rb \op{H}_\mathrm{el} \lb \Phi_a^r\rr\\
&amp;&amp; E &amp;= \ll \phi_a \rb \op{H}^\mathrm{c} \lb \phi_r \rr + 
     \sum_j^{N/2} \ll \phi_a\rb \left(2\op{J}_j -\op{K}_j \right) \lb \phi_r \rr\\
&amp;&amp; E &amp;= \ll \phi_a \rb \op{F}_j \lb \phi_r\rr\\
\text{with}&amp;&amp; \op{F}_i\phi_i &amp;= \varepsilon_i\phi_i\\
\text{and}&amp;&amp; \ll \phi_j \rb \op{F}_i \lb \phi_i \rr 
          &amp;= \varepsilon_i \ll \phi_j | \phi_i \rr = \varepsilon_i\delta_{ij} \\
&amp;&amp; E &amp;=\varepsilon_j\delta_{ar} = 0
\end{align}

The direct consequence and therefore significance of this is that for any post-HF method the singly excited determinants only mix indirectly with the ground state. This simplifies a couple of the integral evaluations.

The remaining question to solve is why the Fock matrix needs to be diagonal. Even though the equation
$$\op{F}_i\phi_i = \varepsilon_i\phi_i
     \tag{1}\label{fock-pseudo}$$
suggests and eigenvalue problem, it is not. Remember the definition of the Fock operator and the operators contained
\begin{align}
  &amp;&amp; \op{F}_i &amp;= \op{H}^\mathrm{c} + \sum_j (\op{J}_j - \op{K}_j),\\
\text{with}&amp;&amp; 
     \op{J}_j\lb \phi_i\rr &amp;=
       \ll \phi_j(\op{x}_1) \rb r_{12}^{-1} 
       \lb \phi_j(\op{x}_1) \rr \lb \phi_i(\op{x}_2) \rr,\\
\text{and}&amp;&amp;
     \op{K}_j\lb \phi_i\rr &amp;=
       \ll \phi_j(\op{x}_1) \rb r_{12}^{-1} 
       \lb \phi_i(\op{x}_1) \rr \lb \phi_j(\op{x}_2) \rr.
\end{align}
As you can see, the "one-electron" Fock operator depends on the solution of all "one-electron" Fock operators (ref. Szabó-Ostlund p. 115). The only way to achieve self-consistency and therefore $\eqref{fock-pseudo}$ is to use unitary transformation and diagonalise the Lagrange multipliers from
$$\sum_j \lambda_{ij} \lb \varphi_j \rr =
  \op{F}_i \lb \varphi_i \rr.\tag{2}\label{fock-lagrange}$$

In other words, the Fock operator is not actually associated with the total energy, but only with the variation of it (due to the Lagrange minimisation). To know one orbital you have to know all orbitals, and to know one orbital energy, you have to know all orbital energies. The Hamilton operator is not the sum of all Fock operators, and the total HF energy is not the sum of all orbital energies.

Therefore the Fock operator is also dependent only on the total wave function and any unitary transformations of the canonical orbitals will retain the total energy. However, the canonical orbitals are the only ones for which $\eqref{fock-pseudo}$ holds.