Representation theorems for groups
There are two baffling representation theorems for groups:
Every group is isomorphic to the automorphism group of some graph. (see Frucht's theorem)
Every group is isomorphic to the fundamental group of some topological space.
I have two questions:
Is there a "deep" connection between these two theorems?
Are there more examples of this kind of representation theorems for groups?
Neither of the theorems you mention is actually particularly deep. The connection between them is the idea of a Cayley graph.
Recall that, if $G$ is any group and $S$ is a generating set for $G$, the Cayley Graph $\Gamma(G,S)$ is defined as follows:
$\Gamma(G,S)$ has one vertex for each element of $G$.
Two vertices $g_1,g_2\in G$ are connected by an edge in the Cayley graph if $g_1 = g_2s$ (or $g_2 = g_1s$) for some $s\in S$.
For example, the Cayley graph of $\mathbb{Z}\times\mathbb{Z}$ with respect to the generating set $\{(1,0),(0,1)\}$ is an infinite rectangular grid.
Now, one of the most important properties of the Cayley graph is that the group $G$ acts on $\Gamma(G,S)$ by automorphisms. This is the "left action": if $g\in G$, then $g$ maps each vertex $g'$ to $gg'$, and maps each edge $(g',g's)$ to $(gg',gg's)$. For example, $\mathbb{Z}\times\mathbb{Z}$ acts on the infinite grid by translations, with $(1,0)$ corresponding to a horizontal translation, and $(0,1)$ corresponding to a vertical translations.
Of course, it is not true in general that $G$ is the full automorphism group of the Cayley graph. For example, there are more automorphisms of an infinite grid than just translations (e.g. reflections and rotations). This is because the Cayley graph actually has more structure than just a graph. Specifically, the Cayley graph is a labeled, directed graph: each edge $(g,gs)$ can be directed to point from $g$ to $gs$, and can be labeled by the generator $s$. What is true is that $G$ is the full group of label and direction-preserving automorphisms of the Cayley graph.
For the first theorem you mention (Frucht's Theorem), all that is required is to modify the Cayley graph in such a way that the directions and labels become part of the graph. For example, we could replace each horizontal edge of a grid by a certain pattern of edges that somehow points "right", and each vertical edge by a different pattern of edges that somehow points "up". In this case, the resulting graph will have automorphism group $\mathbb{Z}\times \mathbb{Z}$. Getting the details of this to work in general is a bit messy, but there's nothing deep about it—we just need to find any viable scheme to encode a directed, labeled graph as a graph.
The second theorem you mention is also related to Cayley graphs, but in a roundabout way. Here is the standard procedure for producing a space whose fundamental group is a given group $G$:
Start by finding a presentation for $G$, with generating set $S$ and relations $R$.
Make a cell complex $X$ with a single vertex $v$, one loop at $v$ for each generator, and one 2-cell for each relation. Then $\pi_1(X)\cong G$. (The space $X$ is sometimes called a presentation complex for $G$.)
For example, one presentation for $\mathbb{Z}\times \mathbb{Z}$ is: $$ \mathbb{Z}\times\mathbb{Z} \;\cong\; \langle r,s \mid rsr^{-1}s^{-1}=1\rangle $$ Here $r=(1,0)$ and $s=(0,1)$, and the relation says that they commute. The resulting complex has a single vertex $v$, two loops at $v$ (one for $r$ and one for $s$), and a single 2-cell attached along the path $rsr^{-1}s^{-1}$. This is a torus, whose fundamental group is isomorphic to $\mathbb{Z}\times\mathbb{Z}$.
Now, here is the connection with Cayley graphs: the universal cover of the complex $X$ is a cell complex whose 1-skeleton is the Cayley graph of $G$! For example, the universal cover of the torus described above is a cell structure on the plane whose 1-skeleton is an infinite grid.
Stated differently, a Cayley complex for a group $G$ is a cell complex whose $1$-skeleton is a Cayley graph, but which has $2$-cells sewn in along each of the relations. (For example, the Cayley complex for $\mathbb{Z}\times\mathbb{Z}$ is the cell structure on the plane whose $1$-skeleton is an infinite grid.) Note that the $2$-cells "fill in the holes" of the Cayley graph, so the resulting space is simply connected. Then the action of $G$ on the Cayley graph extends to an action of $G$ on the Cayley complex, and the quotient of the Cayley complex by this action is the space with fundamental group $G$ described above.
Actually, you don't even need to know a presentation for $G$ beforehand to carry out this construction. Starting with the Cayley graph, you can just attach families of $2$-cells in an equivariant way until the resulting complex is simply connected. Once you are done, the quotient of this complex by the action of $G$ will have fundamental group $G$. (This is a good way to discover a presentation for a group—just add families of 2-cells to the Cayley graph until you get something simply connected, and then each family you added correspond to one relation.)
Edit: By the way, as far as representations theorems for groups go, one of my favorites is that every finitely-presented group is the fundamental group of some $4$-manifold. See this MathOverflow question for some simple proofs.
Another one is the fact that every group is the fundamental group of a space whose universal cover is contractible. These are called Eilenberg-MacLane spaces, and the construction is similar to the construction of the presentation complex given above, except that you also have to add $3$-cells, and then $4$-cells, and so forth to the Cayley complex until it has no "holes" left of any kind. These spaces are very important in algebraic topology, because they turn out to be an embedding of the category of groups and homomorphisms into the homotopy category. The homology and cohomology of these spaces leads to the homology and cohomology of groups
To the 2nd question:
Every group is isomorphic to an automorphism group of some (universal) algebra (G.Grätzer, Universal Algebra, Chapt.1, §12, Cor.1).