How large can the outer automorphism group be? You can make the outer automorphism group very large by taking G be to be a vector space (say over a finite field) so that if |G|=q^n, then Out(G)=GL_n(F_q) of size exponential in n.

Step 1
This only answers your first question. The groups $({\mathbb{Z}}_2{)}^k$ have the fastest growing (outer) automorphism groups possible.
We can derive a pretty good upper bound on the size of automorphism groups. In particular, first note that if G is a finite group with n elements, then it has a generating set S of size at most ${\log }_2<!--\; \; -->(n)$ - we can find such a generating set just by a greedy algorithm in which we start with the empty set, then repeatedly add elements not yet generated until we hit the whole group.
Then, since a group homomorphism is determined by its values on a generating set, there are at most $n^{{\log }_2<!--\; \; -->(n)}$ endomorphisms of a group G. Note that if $G=({\mathbb{Z}}_2{)}^k$, then G has exactly $n^{{\log }_2<!--\; \; -->(n)}=2^{k^2}$ endomorphisms and these are the only groups for which this bound is tight (since the bound on the size of the generating set is only tight if no element has order $>2$).
The number of automorphisms of $G=({\mathbb{Z}}_2{)}^k$ is
$$(2^k-<!--\; -\; -->2^0)(2^k-<!--\; -\; -->2^1)\cdots <!--\; \cdots \; -->(2^k-<!--\; -\; -->2^{k-<!--\; -\; -->1})=2^{k^2}\cdot <!--\; \cdot \; -->\underset{i=1}{\overset{k}{\prod <!--\; \prod \; -->}}(1-<!--\; -\; -->2^{-<!--\; -\; -->i}).$$
Since $\underset{i=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\prod <!--\; \prod \; -->}}(1-<!--\; -\; -->2^{-<!--\; -\; -->i})$ converges to some positive quantity c, the asymptotic growth of the number of (outer) automorphisms of this family of groups grows as $c\cdot <!--\; \cdot \; -->n^{{\log }_2<!--\; \; -->(n)}$, which is a constant factor beneath the theoretical upper bound.
Step 2
Addendum: Refining the argument slightly actually shows a tighter bound and shows that the groups $({\mathbb{Z}}_2{)}^k$ simply have the largest automorphism groups of groups of the same size. In particular, let G be a group. Pick some minimal generating set $g_1,\dots <!--\; \dots \; -->,g_n$ and define $G_i=⟨<!--\; ⟨\; -->g_1,\dots <!--\; \dots \; -->,g_i⟩<!--\; ⟩\; -->$.
Let $n_i$ be the number of injective homomorphisms $G_i\to <!--\; \to \; -->G$ for each i. Clearly $n_0=1$. Then, observe that $n_{i+1}\le <!--\; \le \; -->n_i\cdot <!--\; \cdot \; -->(|G|-<!--\; -\; -->|G_i|)$ since injective homomorphisms $G_i\to <!--\; \to \; -->G$ may be identified with a subset of pairs of injective homomorphisms $f:G_{i-<!--\; -\; -->1}\to <!--\; \to \; -->G$ and elements $g\in <!--\; \in \; -->G\setminus <!--\; \setminus \; -->f(G_{i-<!--\; -\; -->1})$. Using that the size of the groups |Gi| must be an ascending tower of divisors of |G|, one can derive better bounds on the number of automorphisms - these bounds will be tight for all vector spaces.
In fact, no other groups can make the suggested upper bound hold as an equality: A group for which this bound is tight has the property that its automorphism group acts transitively on the non-identity elements. This means every non-identity element has order p for some prime. However, p-groups have a non-trivial center and automorphisms preserve the center. By transitivity, this means that the group must be abelian - which leaves only the finite vector spaces as candidates.