After consulting another post on this website, e.g., here Proving that ${\rm Aut}(S_3)$ is isomorphic to $S_3$, I've come up with a proof that $S_3 \simeq {\rm Aut}(S_3)$. Could someone look it over to tell me if there are any holes? I don't know if my proof of surjectivity is the best way to go about it. It almost feels like "cheating."
I claim that $\phi: S_3 \to \mathrm{Aut}(S_3)$ sending $g \longmapsto c_g (x) = gxg^{-1}$ is an isomorphism. In general, $\phi: G \to \mathrm{Aut}(G)$ sending $g \longmapsto c_g$ is a homomorphism, so it suffices to show that $\phi$ is a bijection. We have: \begin{align*} g \in \mathrm{ker}(\phi) & \iff \phi(g) = c_g (x) = x, \; \forall x \in G \\ & \iff gxg^{-1} = x, \; \forall x \in G \\ & \iff gx = xg, \; \forall x \in G \\ & \iff g \in Z(G) = \{e\}, \end{align*} so the kernel of $\phi$ is trivial, so $\phi$ is injective. Since $S_3$ has exactly $6$ elements which must be sent to distinct elements of the ${\rm Aut}(S_3)$, this implies that $|{\rm Aut}(S_3)| \leq 6$. I claim that $\phi$ is also surjective. We have $S_3 = \langle a = (12), b = (13), c = (23) \rangle$, each of which has order $2$. Since an automorphism $f \in{\rm Aut}(S_3)$ must preserve the order of elements, $f$ must send transpositions to transpositions. Furthermore, upon fixing where $f$ send these transpositions, the rest of the map is determined. Since there are $3!$ possibilities for where to send the permutations and these are the only possible automorphisms, we have $|{\rm Aut}(S_3)| \leq 6$. Hence, $|{\rm Aut}(S_3)| = 6$. But $\phi(S_3) \leq \text{Aut}(S_3)$, so that they have the same order immediately implies that $\phi(S_3) = \text{Aut}(S_3)$, so $\phi$ is surjective, hence bijective.