Last year I attended a first course in the representation theory of finite groups, where everything was over C. I was struck, and somewhat puzzled, by the inexplicable perfection of characters as a tool for studying representations of a group; they classify modules up to isomorphism, the characters of irreducible modules form an orthonormal basis for the space of class functions, and other facts of that sort.

To me, characters seem an arbitrary object of study (why take the trace and not any other coefficient of the characteristic polynomial?), and I've never seen any intuition given for their development other than "we try this, and it works great". The proof of the orthogonality relations is elementary but, to me, casts no light; I do get the nice behaviour of characters with respect to direct sums and tensor products, and I understand its desirability, but that's clearly not all that's going on here. So, my question: is there a high-level reason why group characters are as magic as they are, or is it all just coincidence? Or am I simply unable to see how well-motivated the proof of orthogonality is?

Orthogonality makes sense without character theory.  There's an inner product on the space of representations given by $\dim \operatorname {Hom}(V, W)$.  By Schur's lemma the irreps are an orthonormal basis.  This is "character orthogonality" but without the characters.

How to recover the usual version from this conceptual version?  Notice $$\dim \operatorname{Hom}(V,W) = \dim \operatorname{Hom}(V \otimes W^*, 1)$$ where $1$ is the trivial representation.  So in order to make the theory more concrete you want to know how to pick off the trivial part of a representation.  This is just given by the image of the projection $\frac1{|G|} \sum_{g\in G} g$.
The dimension of a space is the same as the trace of the projection onto that space, so 
$$
\def\H{\rule{0pt}{1.5ex}H}
\dim \operatorname{Hom}(V \otimes W^*, 1) = \operatorname{tr}\left(\frac1{|G|} \sum_{g\in G} {\large \rho}_{\small V \otimes W^*}(g)\right) 
= \frac1{|G|} \sum_{g\in G} {\large\chi}_{V}(g)\ {\large\chi}_{W}\left(g^{-1}\right)
\\
$$ using the properties of trace under tensor product and duals.
