If $G$ is a finite group and $A \subseteq G$ a set of generators, the diameter $diam(G,A)$ is the least integer $d$ such that $A^d=G$.
Now consider the symmetric group $S_n$ and the subset $A_n = \{(12...n), (12) \}$. It is known that $diam(S_n,A_n) \asymp n^2$.
There exist a set of generators $A_n$ of bounded cardinality such that $diam(S_n,A_n) \ll n \log n$?
If $\lvert A_n\rvert=m$, then we have $\lvert A_n^n\rvert\le m^n$. But if $m$ is bounded, this grows more slowly than $n!$.
Edit: The question has changed. $n\log n$ is attainable, with $\lvert A_n\rvert=3$. The idea is to consider the set of $n$ points being moved as $\mathbb{Z}_{n-1}\cup\{\infty\}$. Then you define two linear transformations $\sigma_0,\sigma_1$ on $\mathbb{Z}_{n-1}$ such that you can go from $0$ to any other $m\in\mathbb{Z}_{n-1}$ in $\log n$ steps. The third generator is the transposition $(0,\infty)$.
Then you can get any transposition $(m,\infty)$ in $\log n$ steps, and since $(m,n)=(m,\infty)(n,\infty)(m,\infty)$, and you can write any permutation with $n$ transpositions, the diameter is $n\log n$.
The source for this is the paper On the diameter of finite groups (PDF), section 4.