I've accepted Harald Hanche-Olsen's answer to this question. However, I feel that it needs a little expansion to explain exactly why. The short reason is that his answer triggered a connection in my brain that meant that a few idiosyncrasies of Hilbert spaces suddenly became clear. I'd like to explain them. I should add that I fully expected this question to be one of those where there wasn't a "right" answer.
The key point was that his answer made me think about the rank one case where everything is much simpler. As he said, a vector in $H$ "is" a linear map $\mathbb{C} \to H$, $t \mapsto t \eta$. Similarly, a functional on $H$ is a linear map $H \to \mathbb{C}$. Riesz rep says that such a functional is of the form $\xi \mapsto \langle \eta, \xi \rangle$. Put them together and you find that rank one operators $H \to H$ are of the form $\xi \mapsto \langle \eta, \xi\rangle \zeta$. Or in "bra-ket" notation, $|\xi\rangle \mapsto |\zeta\rangle \langle \eta | \xi \rangle$. So the operator is $|\zeta \rangle \langle \eta|$.
Next is to think about adjoints. What's the adjoint of this operator? Simple: swap everything around. So $|\zeta \rangle \langle \eta|^\star = |\eta \rangle \langle \zeta|$. From this we can deduce that "self-adjoint" means "$\eta = \zeta$", "skew-adjoint" means "$\eta = i\zeta$", whilst "normal" is a little more complicated.
However, this doesn't feel very insightful. The "click" was to think about $|\zeta \rangle \langle \eta|$ and $|\eta \rangle \langle \zeta|$ and try to work out what the swap operation was doing. The block, for me, on why this is purely an algebraic thing and not at all geometric is that the representation of functionals as "inner-product-with-vector" is one of those "it just works" theorems, with little insight as to why it works (yes, yes, I know why, I just don't know why). But if one removes Riesz Representation altogether then one is simply working in a Banach space and adjoints don't exist. So I needed to remove the conclusion of Riesz Rep, but leave enough of it to still ensure that I know I'm in a Hilbert space.
The key step in Riesz Rep is the complementary subspace property: that each subspace has a complement (turns out that this characterises Hilbert spaces, as proved by Lindenstrauss and Tzafriri in 1971). This is much more intuitive for me: it's geometric.
So when we think of a rank one linear transformation on $H$, we have two obvious subspaces: the image and the kernel. The image has dimension $1$, the kernel has codimension $1$. The complementary subspace property then implies that each of these has a complement, the complement of the image being of codimension $1$ and of the kernel being dimension $1$. So up to scalar, these specify another linear transformation. And that linear transformation is the adjoint. Then everything else falls into place.
So the key, for me, is that the fact that $\ker A^\star = (\operatorname{Im} A)^\perp$ and vice versa is not a happy consequence of adjoints but rather the almost defining property.
That "almost" rescues me a little from having missed this before. The phrase "up to scalar" that I highlighted above is important. To get the true adjoint one has to do a little more work to show that there is an operator that satisfies this "almost defining" property and that the map $T \mapsto T^\star$ is "nice" - it's easier to go the other way around and start with the adjoint and work backwards.
Or one could do something a little different. Instead of saying "this works up to scalars, can we fix that?" we should say "this works up to scalars, so let's ignore scalars" and, being Good Geometers and Topologists we know how to do that! Work with projective spaces, and more generally with Grassmannians.
Concentrating again on rank one operators, we have that their images lie in $\mathbb{P}H$ and their kernels in $\mathbb{P}^{\infty - 1}H$ (closed codimension 1 subspaces), so up to scalars, a rank one operator is a point in $\mathbb{P}H \times \mathbb{P}^{\infty -1}H$. The crucial fact that the closest point property gives is that $\mathbb{P}H \cong \mathbb{P}^{\infty - 1}H$ (Riesz Rep is then the trivial observation that $\mathbb{P}^{\infty - 1}X \cong \mathbb{P}X$ for any normed vector space $X$). So really a rank one operator is a point in $\mathbb{P}H \times \mathbb{P}H$. Adjunction is then the obvious $\mathbb{Z}/2$ action on this.
It's not difficult to extend this to any finite rank operator, as Harald says. The question is to make the leap to infinite. At this point, Harald says:
Admittedly, from here to infinite rank is something of a stretch, but I think it might help anyhow.
which just goes to show that he doesn't know his own brilliance. The amazing thing is that there is no stretch! In a Hilbert space we have the approximation property which says that every continuous linear operator is the weak limit of a sequence of finite rank operators. Since adjunction is a weak property - in that you know that you have the adjoint if a load of evaluations say that you do - if I have a weakly convergent sequence of operators then the adjoints weakly converge to the adjoint! And once I have the adjoint, it is the adjoint no matter how bizarrely I found it.
In conclusion, it was Harald Hanche-Olsen's answer that triggered this in my brain so he gets the "accepted" tag. It may not be the "right" answer, but it was the answer that taught me a heck of a lot about something that I thought I knew a lot about already.
(PS Obviously, this answer is community wiki so voting for it gains me no rep and merely says that you agree with or like what I've said. However, if you do like this answer enough to vote for it, you should vote for Harald's answer as well since that sparked all of this one.)
