Smallest permutation representation of a finite group?

It is difficult to find this number for arbitrary finite groups, but many families have been solved. A somewhat early paper that has motivated a lot of work in this area is:

Johnson, D. L. "Minimal permutation representations of finite groups." Amer. J. Math. 93 (1971), 857-866. MR 316540 DOI: 10.2307/2373739.

This paper classifies those groups for which the regular permutation representation is the minimal faithful permutation representation (cyclic of prime power order, K4, or generalized quaternion) and some results on nilpotent groups (improved in later papers).

The minimal permutation degrees of the finite simple groups are known from:

Cooperstein, Bruce N. "Minimal degree for a permutation representation of a classical group." Israel J. Math. 30 (1978), no. 3, 213-235. MR 506701 DOI: 10.1007/BF02761072.

This paper only finds the degrees. A fuller description of the permutation representations are given in:

Grechkoseeva, M. A. "On minimal permutation representations of classical simple groups." Siberian Math. J. 44 (2003), no. 3, 443-462 MR 1984704 DOI: 10.1023/A:1023860730624.

There are a great deal of topics associated with minimal permutation degrees. I'll just briefly sketch them below, let me know if any interest you and I can give citations or longer descriptions:

The minimal degree of a subgroup is never larger than the minimal degree of the parent group, but the minimal degree of a quotient group may be much, much larger than that of the original. This poses problems in computational group theory, since quotient groups may be difficult to represent. Some quotients are easy to represent, and this has had a significant impact on CGT in the last 10 years or so.

Finding minimal permutation representations of covering groups can be difficult, and here I think the results are much less complete. Basically what you want are large subgroups not containing normal subgroups. In a covering group Z(G) is contained in really quite a few of the "good choices". This is because it is contained in Φ(G), the Frattini subgroup, the intersection of the maximal subgroups. One has to give up using maximal subgroups (at least if Z(G) is cyclic of prime power order), and so the minimal degree can increase dramatically.

Minimal degrees of primitive permutation groups is a topic with a different flavor (rather than specific families of groups, it is more of the interactions between group properties), but a great deal is known. Similar techniques are used to describe asymptotic behavior of minimal degrees of arbitrary families of finite groups, and quite powerful results are available there.

Although tighter results may be available for specific classes of groups (as in the comments and other answer), Babai, Goodman, and Pyber [1] showed that in some sense - made precise in the result below - the only obstacle to having a small faithful permutation representation is having a prime-power cyclic group of small index.

Quoting the main result from the abstract:

Let $\mu(G)$ be the smallest degree of a faithful permutation representation of $G$, and let $i(G)$ be the index of its largest cyclic subgroup of prime-power order. Then $i(G) \geq |G| / \mu(G) \geq \exp(c \sqrt{\log i(G)})$ for some constant $c > 0$.

Rephrasing in terms of bounds on $\mu(G)$, this gives

$$ |G|/\exp(c \sqrt{\log i(G)}) \geq \mu(G) \geq |G| / i(G)$$

[1] László Babai, Albert J. Goodman & László Pyber. On faithful permutation representations of small degree. Comm. Alg., 21(5):1587-1602, 1993. doi:10.1080/00927879308824639