The number of automorphisms of the group $C_n$ is $|\text{Aut}(C_n)|= \varphi(n)$, the number of generators of the group. Using GAP, I have checked that this is minimal among groups of order $n$ for every $n<128$, and it feels very plausible that this always holds.
However, I haven't managed to show this is the case; the fact that a group can have elements of high order fixed by every automorphism seems like an obstacle to several approaches. A proof, or references to a theorem implying this, would be welcome.
Googling “groups with small automorphism group” quickly led me to this write-up by Robert Wilson.
As stated in theorem 1, for finite abelian groups we have $|\mathrm{Aut}(G)|\geq|\phi(|G|)|$, with equality if and only if $G$ is cyclic.
As noted immediately after, whether the conclusion was true if we drop the assumption that $G$ is abelian was question 15.43 of the Kourovka Notebook, there attributed to M. Deaconescu.
He asked: (i) Does $|\mathrm{Aut}(G)|\geq|\phi(|G|)|$ hold for every finite group $G$? and (ii) If $|\mathrm{Aut}(G)|=\phi(|G|)$, must $G$ be finite cyclic?
The answer is “No” to both parts. Counterexamples to the first question (what you are asking), emerged from quasisimple groups in the Atlas. In particular, $G=12M_{22}$ (where $M_{22}$ is the Mathieu group on 22 letters) has $\phi(|G|)/|G| = \frac{16}{77}$, and $|\mathrm{Aut}(G)|/|G|=\frac{1}{6}$, which is smaller.
The full citation for the paper referenced in that write-up is:
J.N. Bray, R. A. Wilson. On the orders of automorphism groups of finite groups, Bull. London Math. Soc. 37 no. 3 (2005), pp. 381-385.