Upper bounds on the size of $\operatorname{Aut}(G)$ Any automorphism of a group $G$ is a bijection that fixes the identity, so an easy upper bound for the size of $\operatorname{Aut}(G)$ for a finite group $G$ is given by 
\begin{align*}\lvert\operatorname{Aut}(G)\rvert \leq (|G| - 1)! \end{align*}
This inequality is an equality for cyclic groups of orders $1$, $2$ and $3$ and also the Klein four-group $\mathbb{Z}_2 \times \mathbb{Z_2}$. I think it's reasonable to believe that they are the only groups with this property. The factorial $(|G| - 1)!$ is eventually huge. I searched through groups of order less than $100$ with GAP and found no other examples.
The problem can be reduced to the abelian case. We can check the groups of order $< 6$ by hand. Then if $|G| \geq 6$ and the equality holds, we have $\operatorname{Aut}(G) \cong S_{|G|-1}$. Now $\operatorname{Inn}(G)$ is a normal subgroup of $\operatorname{Aut(G)}$, and is thus isomorphic to $\{(1)\}$, $A_{|G|-1}$ or $S_{|G|-1}$. This is because $A_n$ is the only proper nontrivial normal subgroup of $S_n$ when $n \geq 5$. We can see that $(|G| - 1)!/2 > |G|$ and thus $\operatorname{Inn}(G) \cong G/Z(G)$ is trivial.
How to prove that there are no other groups for which the equality $\lvert\operatorname{Aut}(G)\rvert = (|G| - 1)!$ holds? Are any better upper bounds known for larger groups?
 A: Consider $G$ as a subgroup of $S_{|G|}=S$ via the regular representation.  Then the normalizer of $G$ is the holomorph of $G$, and saying $|Aut(G)|=(|G|-1)!$ is the same as saying that $N_S(G)=S$.  In other words, $G$ is a normal subgroup of order $n$ in $S_n$. This can only happen for $n<5$, and you get the following four groups:
trivial, order 2, order 3, Klein 4.
A: Well, for starters, to get equality you would need every element to have the same order, and so that order is a prime (so your group has prime-power order).
You should next realise that if you have equality then you must have equality in $C_p$, the cyclic group of order $p$, as there must exist a homomorphism which switches every element of $\langle g\rangle$, where $g$ is an element of order $p$, and keeps every other element in you group fixed. Clearly this doesn't happen if $p=2$ or $p=3$.
For $p=2$, notice that is doesn't work for $C_2\times C_2\times C_2$, but that the observation in the above paragraph still must hold (that you can restrict to subgroups and still get an automorphism).
For $p=3$, notice that is doesn't work for $C_3\times C_3$, but that the observation in the above paragraph still must hold (that you can restrict to subgroups and still get an automorphism).
A: Even without the classification of finite simple groups, quite reasonable bounds are known, for example in work of P.M. Neumann. If the group $G$ can be generated by $r$ but no fewer elements, then no automorphism of $G$ can fix the $r$ given generators, so there are at most $\prod_{j=1}^{r} (|G|-j)$ different automorphisms of $G,$ since the $r$ generators must have distinct images, none of which is the identity. As P.M. Neumann has observed, $G$ can always be generated by ${\rm log}_{2}(|G|)$ or fewer elements, so we have $r \leq \lfloor {\rm log}_{2}(|G|) \rfloor .$ For $|G| >4,$ this always gives a strictly better bound for the size of ${\rm Aut}(G)$ than $(|G|-1)!.$ For large $|G|,$ it is much better. Using the classification of finite simple groups, much better bounds are known.
Later edit: Perhaps I could outline Neumann's argument, since it is quite elementary, and I do not remember a reference: Let $\{x_1, x_2, \ldots, x_r \}$ be a minimal generating set for $G$ and let $G_i = \langle x_1, x_2, \ldots, x_i \rangle $ for $i >0,$ $G_{0} = \{ e \}.$ Then for $1 \leq i \leq r,$ we have $|G_i| > |G_{i-1}|$ by minimality of the generating set. Furthermore, $|G_i|$ is divisible by $|G_{i-1}|$ by Lagrange's theorem, so $|G_i| \geq 2|G_{i-1}|.$ Hence $|G| = |G_r| \geq 2^r.$
A: I am quite late here, but perhaps the result is worth mentioning.
For each prime power $q=p^k$, define $\theta(q) = \lvert \operatorname{GL}_k(p)\rvert$, the order of $\operatorname{Aut}(C_p^k)$. For a positive integer $n=p_1^{a_1}\ldots p_k^{a_k}$ let $\theta(n) = \prod_{i=1}^k\theta(p_i^{a_i})$. So $\theta(n)$ is basically the order of the automorphism group of the unique elementary abelian group of order $n$. (I am abusing terminology a little here by calling a group elementary abelian if it is a direct product of elementary abelian groups in the usual sense.)
Now, as to your second question, Peter Neumann has shown that for a finite group $G$ of order $n$, $\lvert\operatorname{Aut}(G)\rvert$ divides $|G/Z(G)|\theta(n)$, or equivalently that $\lvert\operatorname{Out}(G)\rvert$ divides $\theta(n)$. The implied upper bound is sharp since equality is attained infinitely often (for elementary abelian groups).
If $G$ is nilpotent of order $n$ then  $\lvert\operatorname{Aut}(G)\rvert$ divides $\theta(n)$. See here for a proof. In that same paper, Birkhoff and Hall show that if $G$ is soluble of order $n$ then $\lvert\operatorname{Aut}(G)\rvert$ divides $n\theta(n)$. Neumann improves this by showing that if $G$ is soluble of order $n=p_1^{a_1}\ldots p_k^{a_k}$ and $P_i \in \operatorname{Syl}_{p_i}(G)$ for $i \leq k$, then $\lvert\operatorname{Aut}(G)\rvert$ divides $|G/Z(G)|\cdot \prod_{i=1}^k\lvert\operatorname{Aut}(P_i)\rvert$. The proof of that last result (which is basically a lemma in Suzuki's "Group Theory II") is very cool.
A: I think I have found a different solution. Is this correct?
Suppose that $G$ is a group and $|G| > 4$. To prove that $|\operatorname{Aut}(G)| < (|G| - 1)!$, it is enough to find a bijection $f: G \rightarrow G$ with $f(1) = 1$ that is not an automorphism. 
First of all, let $a$ be some nonidentity element of $G$. Let $b \in G \backslash \{1, a, a^{-1}\}$ and $x \in G \backslash\{1,a,b, ab\}$. Define the map $f: G \rightarrow G$ by $f(ab) = x$, $f(x) = ab$ and $f(g) = g$ for rest of the elements in $G$. Then $f$ is a bijection that fixes $1$, but $f(ab) \neq f(a)f(b)$ because $x \neq ab$.
A: I believe this is an exercise in Wielandt's permutation groups book.
$\newcommand{\Aut}{\operatorname{Aut}}\newcommand{\Sym}{\operatorname{Sym}}\Aut(G) \leq \Sym(G\setminus\{1\})$ and so if $|\Aut(G)|=(|G|-1)!$, then $\Aut(G) = \Sym(G\setminus\{1\})$ acts $|G|-1$-transitively on the non-identity elements of G.  This means the elements of G are indistinguishable.  Heck even subsets of the same size (not containing the identity) are indistinguishable. I finish it below:

 In particular, every non-identity element of G has the same order, p, and G has no proper, non-identity characteristic subgroups, like $Z(G)$, so G is an elementary abelian p-group.  However, the automorphism group is $\newcommand{\GL}{\operatorname{GL}}\GL(n,p)$ which, for $p \geq 3, n\geq 2$, only acts at most $n-1$-transitively since it cannot send a basis to a non-basis.  The solutions of $p^n-1 \leq n-1, p \geq 3, n \geq 2$ are quite few: none.  Obviously $\GL(1,p)$ has order $p-1$ which is very rarely equal to $(p-1)!$, when $p=2, 3$.  $\GL(n,2)$ still can only act $n$-transitively if $2^n-1 > n+1$, since once a basis's image is specified, the other points are determined, and the solutions of $2^n-1 \leq n+1$ are also limited: $n=1,2$.  Thus the cyclic groups of order 1,2,3 and the Klein four group are the only examples.

