I haven't heard this question before, but I would approach it in a following way: you know some basic relations between irreducible representations of a groups — e.g. their # is the # of conjugacy classes — and let's say we've written the kernels of representations and their dimensions. The generating function (*) that counts all representations is $((1-x^{r\_1})(1-x^{r\_2})\dots (1-x^{r\_k}))^{-1}$ and you're asked to subtract the representations that have nontrivial kernel. This combinatorial problem is partly tractable for a given group, though I don't see a nice closed formula.
The situation simplifies for Abelian groups, and the answer you provide is in the right direction. A semisimple representation of Abelian group is a sum of characters. (I misunderstood what you asked here a bit, but bear with me.) A single character could already be faithful: for example, for $\mathbb Z\_2 \times \mathbb Z\_3 = \mathbb Z\_6$ the irreducible character that hits all 6-roots of unity is a faithful representation. And there are $\varphi(6) = \varphi(3)\cdot\varphi(2) = 2$ of those. Another example: $\mathbb Z\_2\times \mathbb Z\_2$. The same formula doesn't works here as $1\cdot 1 = 1$ but the corresponding representation isn't faithful. For two-dimensional case, you positively get two characters, but there is no reason to expect that there will be a splitting into a character of exactly first summand and exactly second summand. You should, however, be able to calculate it by the method below.
So the formula $\prod\varphi(m\_i)$ will correctly describe the answer only for a case of group having only one invariant factor.
Here's how to make a complete computation for an $n$-dimensional space and the case of $\mathbb Z\_6$. You need to take all representations of it which are neither representations of $\mathbb Z\_2$ nor of $\mathbb Z\_3$. Fortunately, this is easy to write using inclusion-exclusion principle:
$(1 -x)^{-5} - (1-x)^{-1} - (1-x)^{-2} + 1$ and you can simplify this or just get the first three terms:
$1+5x+20x^2 + 5x^2 - 1 - x - x^2 - 1 - 2x - 3x^2 + 1 = 0 + 2x + 21x^2 + \dots$
The 2 here stands for 2 "simple" characters of $\mathbb Z\_6$, while 21, if I made no mistake, is the number of 2-dimensional representations: 19 of them are of the type "character as above $\oplus$ anything" and 2 of the type "character of $\mathbb Z\_2$ $\oplus$ character of $\mathbb Z\_3$ ".
Now I think using the same principle you can actually write a generating function for your sequence with an inclusion-exclusion principle for any group G. Since a representation is faithful iff it doesn't have a kernel, you can enumerate all of your normal subgroups and then find your answer as $F\_G(x) - F\_{G/H\_1}(x) - F\_{G/H\_2}(x) - \dots + F\_{G/H\_1\cup H\_2}(x) + \dots $. Here the notation $F\_G(x)$ is a generating function counting all representations and $H\_1, H\_2, \dots$ are all maximal normal subgroups.
Hope that helps.
Update: I understand now you're interested in a closed formula for a specific case. For example, the computation by the formula above for
$\mathbb Z\_2\times \mathbb Z\_2$ gives $(3\cdot 4)/2 -1 -1 -1 = 3$. The normal subgroups of an Abelian group are not hard to write, so it would be plausible if this could be made into a good formula.
(*) Let me know if you're not familiar with generating functions.
Edit: I now give the argument for general reductive $G$.
Let $G$ be a reductive algebraic group over an alg. closed field $k$ of char. 0. Fix a max
torus $T$ and write $X = X^*(T)$ for its group of characters. Write $R$ for the
subgroup of $X$ generated by the roots of $G$. Then the center $Z$
of $G$ is the diagonalizable subgroup of $T$ whose character group is $X/R$.
Claim: $G$ has a faithful irreducible representation if and only if the character
group $X/R$ of $Z$ is cyclic.
Note for semisimple $G$, the center $Z$ is finite. Since the characteristic of $k$ is 0, in this case the group of $k$-points of $Z$ is (non-canonically) isomorphic
to $X/R$. Thus $Z$ is cyclic if and only $X/R$ is cyclic.
In general, the condition that $X/R$ is cyclic means either that the group of points $Z(k)$ is finite cyclic, or that $Z$ is a 1 dimensional torus.
As to the proof, for $(\implies)$ see Boyarsky's comment following reb's answer.
For $(\Leftarrow)$ let me first treat the case where $G$ is almost simple; i.e. where the root system $\Phi$ of $G$ is irreducible. Supopse that the class of $\lambda \in X$ generates the cyclic group $X/R$. Since
the Weyl group acts on $X$ leaving $R$ invariant, the class of any $W$-conjugate of $\lambda$ is also a generator of $X/R$. Thus we may as well suppose $\lambda$ to be dominant
and non-0 [if $X=R$, take e.g. $\lambda$ to be a dominant root...]
Now the simple $G$-module $L=L(\lambda) = H^0(\lambda)$ with "highest weight $\lambda$"
will be faithful. To see this, note that since $\lambda \ne 0$, $L$ is not the trivial representation. Since $G$ is almost simple, the only proper normal subgroups
are contained in $Z$. Thus it suffices to observe that the action of $Z$ on the
$\lambda$ weight space of $L$ is faithful.
The general case is more-or-less the same, but with a bit more book-keeping.
Write the root system $\Phi$ of $G$ as a disjoint union $\Phi = \cup \Phi_i$
of its irreducible components. There is an isogeny
$$\pi:\prod_i G_{i,sc} \times T \to G$$
where $T$ is a torus and $G_{i,sc}$ is the simply connected almost simple group
with root system $\Phi_i$. Write $G_i$ for the image $\pi(G_{i,sc}) \subset G$.
The key fact is this:
a representation $\rho:G \to \operatorname{GL}(V)$ has
$\ker \rho \subset Z$ if and only if the restriction $\rho_{\mid G_i}$ is non-trivial
for each $i$.
Now, as before pick $\lambda \in X$ for which the coset of $\lambda$ generates
the assumed-to-be cyclic group $X/R$. After replacing $\lambda$ by a Weyl group
conjugate, we may suppose $\lambda$ to be dominant. After possibly repeatedly replacing
$\lambda$ by $\lambda + \alpha$ for dominant roots $\alpha$, we may suppose
that $\lambda$ has the following property:
$$(*) \quad \text{for each $i$, there is $\beta_i \in \Phi_i$ with $\langle \lambda,\beta_i^\vee \rangle \ne 0$}$$
Now let $L = L(\lambda)$ be the simple module with highest weight $\lambda$. Condition
$(*)$ implies that $G_i$ acts nontrivially on $L$ for each $i$, so by the "key fact",
the kernel of the representation of $G$ on $L$ lies in $Z$. but since $\lambda$
generates the group of characters of $Z$, the center $Z$ acts faithfully on the
$\lambda$ weight space of $L$.
Best Answer
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.