I understand that a circulant is expanded as a polynomial in P
$$C = C_{0} P + C_{1} P^{2} + \dots + C_{n} P^{n}$$
I also know that the columns of the Fourier matrix $F$ are the eigenvectors of $P$ and therefore eigenvectors of $C$.
What I don't understand is how $F$ times the coefficients vector $C_{0} C_{1} \cdots C_{n}$ gives the eigenvalues of $C$. Also, because $PF=F\Lambda$, $F^{-1}PF=\Lambda$ gives the eigenvalues of P, what does $FP$ give?
Your last paragraph is the result of an interesting coincidence: it turns out that $F$ is not only the matrix of eigenvectors of $P$, it is also the Vandermonde matrix associated with the eigenvalues of $P$. The Vandermonde matrix has the property that for any values $x_0,x_1,\dots,x_n$ and polynomial $p(x) = a_0 + a_1 x + \cdots + a_nx^n$, we have $$ V(x_0,x_1,\dots,x_n) \pmatrix{a_0\\a_1\\ \vdots \\ a_n} = \pmatrix{p(x_0)\\p(x_1)\\ \vdots \\ p(x_n)}. $$ Now, let $p(x) = C_0 + C_1 x + \cdots + C_n x^n$. Since $F = V(\lambda_0,\lambda_1,\dots,\lambda_n)$ where $\lambda_0,\lambda_1\dots,\lambda_n$ are the eigenvalues of $P$, we have $$ F \pmatrix{C_0\\ C_1 \\ \vdots \\ C_n} = \pmatrix{p(\lambda_0)\\ p(\lambda_1) \\ \vdots \\ p(\lambda_n)}, $$ which are indeed the eigenvalues of the circulant matrix $C = p(P)$.
To figure out what $FP$ is, we could note that $$ FP = (P^TF^T)^T = (P^{-1}F)^T = (F\Lambda^{-1})^T = \Lambda^{-1}F. $$