How small can a group with an n-dimensional irreducible complex representation be? More precisely, what is the smallest exponent e such that, for every n, there exists a group of size at most Cn^e for some absolute constant C and with an n-dimensional irreducible complex representation?  
I know that e ≤ 3.   For various special values of n we can attain the lower bound e ≥ 2.  For example, if n+1 = q is a power of a prime then the group of affine linear transformations ax + b on Fq is doubly transitive, so the linearization of this group action decomposes into the trivial representation and an irreducible representation.
Edit:  Oops.  Reading Noah's comment, I probably should've justified the upper bound.  I hope this example is correct: let zeta be an nth root of unity and consider the group generated by the diagonal matrix (zeta, zeta, ... zeta), the diagonal matrix (1, zeta, zeta^2, ... zeta^{n-1}), and a cyclic permutation matrix of order n.  It can be verified that this is a group of order n^3 and that its elements span M_n(C) , so the given representation is irreducible.
 A: Here's half a proof:
The answer should be e=3.  You've showed that's always realizable, so all I need to do is exhibit infinitely many n so that any group with an n-dim irrep has dimension at least c n^3, for some fixed constant c < 1/2.  All the n's I exhibit will be prime, so let n=p.  I also want that (p-1)/2 is prime.
Assume for contradiction a group G with #G smaller than p^3 and a p-dimensional irrep.  Consider a p-Sylow subgroup of G.  Clearly it has size p or p^2.  In particular there are only three options: Z/p, Z/p^2, and Z/p x Z/p.
If #G_p is p^2, then the number of Sylow p subgroups is congruent to 1 and divides G/p^2 < p.  Hence G_p is a normal subgroup.  The dimension of any irrep of a group always divides the index of any normal abelian subgroup.  Hence G has size at least p^3.
So G_p is Z/p.  If G_p were normal, then by the above fact p would divide its index in G, which is nonsense.  So G_p has kp+1 conjugates.  So the normalizer of G_p has index kp+1.  Now we use that (p-1)/2 is prime to conclude that either G_p is central in its normalizer, or else the normalizer has size at least p(p-1)/2.  In the latter case the whole group has size at least p(p-1)(p+1)/2.
Therefore G_p=Z/p is central in its normalizer so by the Burnside normal complement theorem it has a normal complement and G = N \semidirect Z/p for some normal subgroup N.  By the "transport de structure" theorem from Serre, any irrep of G is either induced from a representation of a proper subgroup H containing N, or else its restriction to N is isotypic.  Since the index of N is p which is the dimension of the irrep, in the first case the rep is induced from a 1-dim irrep of N.  In the latter case, since N has no p-dimensional irreps, the restriction of to N is p copies of a 1-dim irrep.  But by Frobenius reciprocity the induction of this 1-dim rep would contain p copies of our irrep, which is ridiculous.  So our irrep is induced from a 1-dim rep of N.
Now we can replace G with G/[N,N] (which makes sense because a characteristic subgroup of a normal subgroup is normal), and we still have a p-dim rep of G (given by the same induction), and we've shrunk the size. So we can assume that N is abelian.  To finish the proof we need to use the right version of the number theory argument David suggested.
A: I posted a question about primes in arithmetic progressions and was told my understanding is wrong. Although proving this would be harder than the generalized Riemmann hypothesis, the expectation of experts is that, for any n, there is a prime q which is 1 mod n and is O(n^{1+ \epsilon}). In that case, Z/n acting on Z/q would achieve e = 2+\epsilon.
It seems like the best result we are likely to prove is that the only way to beat e=3 is to find a small prime power which is 1 mod n.
A: It looks like you can get around Noah's use of the (ludicrously difficult) conjecture of the existence of infinitely many Sophie Germain primes by appealing to the classification of finite simple groups.
If |G| < cp^3, then (I haven't actually checked this but I believe it to be true) G cannot contain any nonabelian finite simple groups in its Jordan-Hölder decomposition.
Now we use 'transport de structure' (Serre - Linear Represenations of Finite Groups Prop 24). If G has a normal subgroup H of index coprime to p, then the restriction of this irrep to H must be isotypic, hence a sum of one dimensional irreps. This representation then factors through the commutator subgroup [H,H] and since the dimension of an irrep divides the index of a normal abelian subgroup, this implies p divides the index of G in H, a contradiction.
The fact that a cyclic group of order p must appear in the Jordan-Hölder decomposition now implies that a Sylow subgroup has a normal complement so we may rejoin the above argument.
Of course we still need to know how large the size of the smallest prime in an AP is.
A: Given a finite group, the sums of squares of dimensions of irreducible representations add up to the order of the group, so the dimension of an irreducible representation is at most the square root of the order of the group.  If I understand your question correctly, this (together with your Frobenius group lower bound) implies e is 2. (Edit: My argument comes from a misreading of the question, but Noah's comment is sufficiently informative that I don't want to delete the post.)
Noah Snyder has a paper on near-extremal phenomena in this setting:

*

*Groups with a Character of Large Degree, Proc. Amer. Math. Soc. 136 (2008), no. 6, 1893–1903, doi:10.1090/S0002-9939-08-09147-8, arXiv:math/0603239.

A: Note that for every odd prime $p$, the finite group ${\rm PSL}(2,p)$ has an irreducible complex character of degree $p$, and has order $\frac{p(p^{2}-1)}{2}$.  Hence if $n = p_{1}^{a_{2}}\ldots p_{r}^{a_{r}}$ where each $a_{i} \in \mathbb{N}$ and the $p_{i}$ are distinct odd primes, then there is a finite group $G$ of order less than 
$\frac{n^{3}}{2^{t}}$, where $t$ is the number of odd prime divisors of $n$ (counting multiplicities), which has a faithful complex irreducible character of degree $n$. The group $G$ is a direct product of groups of the form ${\rm PSL}(2,p_{i})$
($a_{i}$ factors ${\rm PSL}(2,p_{i})$ for each $i$). If $n$ is as above, and $h = 2^{a}n$ for some positive integer $a$, then we may take the direct product of $a$ copies of ${\rm SL}(2,2)$ with the previous group to obtain a group of order less than $\left(\frac{3}{4}\right)^{a} \frac{h^{3}}{2^{t}}$ with an irreducible character of degree $h$ (and if $h = 2^{a}$, a case which, strictly speaking, we have not yet covered, we obtain a group of order $\frac{2^{3a}3^{a}}{4^{a}}$ with a faithful complex irreducible character of degree $2^{a}$). Actually, since $S_{4}$ has an irreducible character of degree $4$, 
we can find a group of order $(24)^{\frac{a}{2}}$ with an irreducible character of degree $2^{a}$ when $a \geq 2$ is even, which improves $6^{a}.$ Likewise, we can find a group of order $ 6 \times (24)^{\frac{a-1}{2}}$ with an irreducible character of degree $2^{a}$ when $a \geq 1$ is odd, which improves $6^{a}$ for $a \geq 3$ So this improvement could also be used to improve cases when $h$ above is even).
This is only a marginal improvement of the bound obtained by the construction in the question, and does not impact on the optimal choice of $e$ asked for. 
