I consider the situation over $\mathbb{C}$. We can replace $G$ by the subgroup generated by the $g_j$'s, so assume that $G$ is generated by the $g_j$'s. That $G$ contains a spanning set of the space of all matrices yields that the center of $G$ only contains scalar matrices, and also that the inclusion $G \hookrightarrow \operatorname{GL}(n,\mathbb{C}) $ is an absolutely irreducible representation.
That the $g_j$'s modulo the center form a subgroup means that $|G: Z(G)| = n^2$. So $G$ has an irreducible representation of degree $n$ with $n^2 = |G:Z(G)|$. Such groups are called groups of central type. DeMeyer and Janusz (DeMeyer, F. R.; Janusz, G. J., Finite groups with an irreducible representation of large degree, Math. Z. 108, 145-153 (1969). ZBL0169.03502, Theorem 2) have shown that a finite group is of central type if and only if each Sylow $p$-subgroup $S$ of $G$ is of central type and $S\cap Z(G) =Z(S)$. Now a $p$-group always has a nontrivial center of order at least $p$. Thus the center of $G$ has an order divisible by all the primes involved in $n$, and your bound follows.
As you say, there are groups attaining the bound: An extraspecial $p$-group of order $p^{2k+1}$ has an irreducible, faithful representation of dimension $p^k$, and the image is a matrix group as in the question with $n=p^k$. For composite $n=p_1^{k_1}\dotsm p_m^{k_m}$, we take a direct product $P_1 \times \dotsb \times P_m$ , where each $P_i$ is extraspecial of order $p_i^{2k_i+1}$.
The situation should be the same over any field of characteristic zero, because the assumptions in the question yield that the given natural representation is absolutely irreducible, and also over fields such that the characteristic does not divide $n$. When the prime $p$ divides $n$, then my guess is that such a matrix group over a field of characteristic $p$ is not possible.
