I have a solution to the case of a general cyclic quotient.
If $A=Z_n$ is cyclic then we can treat $\phi:G\to Z_n\hookrightarrow\mathbb{C}$ as a one dimensional representation of $G$. We can also form representations $\phi^a$ for $a=0,...,n-1$. These give rise to characters $\chi_a$ for $a=0,...,n-1$. We view these characters as functions from the set $\mathcal{C}$ of conjugacy classes of $G$ to the complex numbers.
First we recall an important fact from the theory of characters of finite groups. If $\chi$ is the character of some representation, then $\sum_{g\in\mathcal{C}}\chi(g)$ is a nonnegative integer. This is because $\sum_{g\in\mathcal{C}}\chi(g)$ is exactly the value of the inner product of $\chi$ with the character associated to the conjugation action of $G$ on $\mathbb{C}[G]$.
For $b\in Z_n$ let $f(b)$ be the number of conjugacy classes of $G$ on which $\chi_1$ takes the value $\zeta_n^b$. So the problem now is to show that each of the $f(b)$ is bounded by $f(0)$. Applying the previously stated fact about group characters to each of the characters $\chi_a$, we have for $a=0,...,n-1$ that $$g(a)=\sum_{b\in Z_n}f(b)e^{2\pi i ab/n}\geq 0.$$ Now Fourier inversion tells us that for $b=0,...,n-1$ we have $$f(b)=\frac{1}{n}\sum_{a\in Z_n}g(a)e^{-2\pi iab/n}.$$ Therefore by the triangle inequality, for any $b$ we have $$f(b)=|f(b)|\leq\sum_{a\in Z_n}g(a)=f(0).$$