About Q1, this is standard. Take a strong generating set. List the strong generators in inverse order of the length of their stabiliser. I.e., first come the generators that fix all but the last point in the base, and last come the generators that move the first element of the base.  Now delete every generator whose cycles are subsets of the orbits of the subgroup generated by the generators coming before it in the list.  You are left with at most $n-1$ generators that still generate the group.  Proof by induction on the length of the base.

Incidentally, programs for computing $Aut(G)$ like nauty, bliss, saucy, always find at most $n-1$ generators.