The quaternion group $Q_8 = \langle x, y \,\vert \, xyx^{-1}y = yxy^{-1}x = 1\rangle$ has $24$ generating pairs, all Nielsen equivalent, and $24$ automorphisms. It looks like a good match, certainly the one with the smallest cardinal.

There is a reason why constructions of the type $G = F_2/K$ with $K$ a verbal subgroup of $F_2$ are not so abundant. For such a group $G$, the automorphism group acts transitively on the set of generating pairs. Because of the surjectivity assumption $Aut(F_2) \twoheadrightarrow Aut(G)$, this implies that $G$ possesses only one Nielsen equivalence class of generating pairs. So does its abelianization $G/[G, G] \simeq C_n \times C_n$ by a famous lemma of Gaschütz. As already noted by Derek Holt, this holds only if $n \in \{1, 2, 3, 4, 6\}$. 

The following article of G. Rosenberger seems to be a reference for this kind of problems: "Automorphismen und Erzeugende für Gruppen mit einer definierenden Relation", 1972. (It may address only infinite groups though).
This article is quoted in "Combinatorial Group Theory" of R. C. Lyndon and P. E. Schupp in Section I.4 and Section II.2; the key word is *quasifree presentation*. In more recent texts, some authors speak about *tame automorphisms*, others about *induced automorphisms*.