A catalog of faithful representations of finite groups?

Dustin, if you know the character $\chi$ of a representation $\rho$ of a finite group, it is easy to see whether it is faithful or not. Your representation is faithful if and only if for every $g \in G$, $\chi(g)=\chi(e)$ implies $g=e$. For if $g \in G$, and $\chi(e)=n$ is the dimension of your representation $\rho$, $\chi(g)$ is the sum of the $n$ eigenvalues of $\rho(g)$, which are roots of unity, hence $|\chi(g)| \leq n$ with equality if and only if all eigenvalues are the same, that is if and only if $\rho(g)$ is scalar, and then $\chi(g)=n$ if and only if $\rho(g)=1$.

So each time you have a table of characters for a group, you know which of its irreducible representations is faithful, and you can easily find the one of smallest dimension. You can find tables of characters in many places, like in the atlas of finite groups already mentioned for certain groups (apparently close to simple groups, so not the one for which your question is the most interesting), or for some noteworthy groups on wikipedia, or on sage by typing G.table_of_characters() if G is your group, etc...

Now as Derek said in comments, that doesn't really answer your initial question of finding the faithful representation of smallest dimension, which may not be irreducible. For this you just have to test with the above criterion the various sums (with repetitions) of irreducible characters, by increasing order of dimension, until you find one that is faithful, which in general should to take too long. This would be easy to program in sage, say...

This is a naive approach of a non-specialist. It is very possible that there are more clever ways to find the smallest dimension of a faithful representation. This suggests many questions -- What can be said about groups such that there smallest faithful representation is irreducible, for instance ? Or, what is the dimension of the smallest faithful representation of, say, $GL_2(\mathbb Z/\ell^n \mathbb Z)$ when $\ell$ is a fixed prime and $n$ varies? In this instance the table of characters has been recently determined, but it is quite complicated and the naive method suggested above seems impractical.

How about the Atlas of Finite Groups ?

It may be useful to note that if $M$ is a subgroup of the finite group $G$ and $M$ contains no non-identity normal subgroup of $G$ then the permutation character of $G$ afforded by the action on the cosets of $M$ is faithful, so subtracting the trivial character gives a faithful complex character of degree $[G:M]-1.$ This usually won't be the minimal degree of a faithful character, but it is a handy upper bound for the minimal degree.