I recommend I.M. Isaacs's Character Theory of Finite Groups to see finite groups from the point of view of their characters.
I couldn't think of a really short example of finding a character table of an unknown group, but I relate a story that can be very briefly summarized as: "Here is an argument in a textbook showing how to uniquely classify two simple groups by the centralizer of an involution. People did that a lot with known simple groups, until Janko found a previously unknown simple group." I only tell the textbook part.
Often we don't need to compute the entire character table to determine how to construct the group. One class of result I found interesting were the "recognition theorems" which often have a large character theory step. However, in order to have an answer that is shorter, I chose an earlier recognition theorem, theorem 7.10 from Isaacs's book:
Suppose a finite perfect group $G=G'$ contains an element $\tau$ of order 2 whose centralizer $C_G(\tau)$ is a dihedral group of order 8. Then $G$ itself must be the 3x3 general linear group $\operatorname{GL}(3,2)$ of order 168, or the degree 6 alternating group $A_6$ of order 360.
Sketch of proof: Let $M \subset D=C_G(\tau)$ be cyclic of order 4 and centralizing $\tau$. Then $M$ is a "trivial intersection" set (similar to Frobenius complements if you've read about those) in that $M \cap M^x = \begin{cases} M & \text{if } x \in N_G(M)=C_G(\tau) \\ 1 & \text{otherwise}\end{cases}$.
Now class functions on $D=C_G(\tau)$ which vanish on $M$ have a very nice isometry property: If $\theta,\phi$ are class functions on $C_G(\tau)$ which vanish on $M$ and $\theta(1)=0$, then the induced character $\theta^G(x) = \theta(x)$ doesn't change for $x\in D$, and moreover neither does the inner product $[\theta^G,\phi^G] = [\theta,\phi]$.
This lets us deduce part of the character table of $G$ from that of $C_G(\tau)$
(I consider that statement to more or less be my answer to your question, but I think it helps to see a little more of how this actually works.)
In particular, take one of the two Galois conjugate faithful linear characters of $M$, call it $\lambda$, then $\theta=(1_M-\lambda)^D$ is a class function on $D$, $\theta(1)=0$, and $\theta$ vanishes on $D \setminus M$ by the formula for induced character. Since $[\theta,\theta]=3$ by an explicit calculation in $D$ (a very small group with an easy character table), we also have $[\theta^G,\theta^G] = 3$ which is now occurring in an unknown group $G$. This means we can write $\theta^G = 1_G + \chi - \psi$ for irreducible characters $\chi,\psi$ of $G$. Since $\theta^G(x) = \theta(x)$ for $x \in D$, we can nearly compute the values of $\chi$ and $\psi$ on $D$!
In $D$, we have $\theta(1)= 0$ and $\theta(\tau)=4$ (again easy calculations in a tiny group), so in $G$ we have $0 = \theta^G(1) = 1 + \chi(1) - \psi(1)$ and $4 = 1 + \chi(\tau) - \psi(\tau)$.
(Isaacs now uses a class function that counts solutions of equations, a technique from Frobenius, to show that:)
$|G|=\dfrac{2^8}{\frac{1^2}{1} + \frac{\chi(\tau)^2}{\chi(1)} - \frac{\psi(\tau)^2}{\psi(1)}}$
A simpler argument shows $|D| \geq 1 + \chi(\tau)^2 + \psi(\tau)^2$
Now a little number crunching finds all possible values of $\chi(\tau)$ and $\psi(\tau)$ which gives all possible orders of $G$: $|G|=168$ or $|G|=360$. Since perfect groups of such small order are quite rare, we have it must be one of the two well-known simple groups.
So this doesn't exactly answer your question: instead of using a character table to find an unkown group, we use it to show a potentially unknown group is actually on old friend. This sort of thing happened several times until Janko accidentally broke it when trying $C_G(\tau) = C_2 \times A_5$ and we found our first new sporadic simple group in a hundred years. The part of the argument I've highlighted here is echoed on page 153 of Janko's 1966 Journal of Algebra paper -- I believe I learned these steps from Suzuki's CA papers, but I can't seem to find my notes at the moment.
Best Answer
You can construct one of these as follows (the other comes, as you observed, by tensoring it with the sign character). Undoubtedly you know that $S_5$ has six Sylow 5-subgroups, each with a normalizer $N$ of order 20. It is easy to convince yourself of the fact that the conjugation action on this set of six elements is doubly transitive. Therefore, by the usual result, this 6-dimensional representation splits into a direct sum of a 1-dimensional trivial representation and a 5-dimensional irreducible one.
This gives, indeed, the exceptional transitive embedding $f$ of $S_5$ in $S_6$. Even more so: by studying the type of elements present in $N$ (and its conjugates), you can deduce a number of things about the cycle structure of elements of $f(S_5)$. Furthermore, $f(S_5)$ obviously has six conjugates in $S_6$. This conjugation action gives rise to the famous non-inner automorphism of $S_6$. Using the bits that you get from the cycle structure of elements in $f(S_5)$ you can deduce that this outer automorphism interchanges the conjugacy classes of $(12)$ and $(12)(34)(56)$ (among other things).