The assertion is true and we do not even need the vector space dimension to be even. I will change a few notations for my convenience, in particular I'll reserve lower case letters for maps and upper case letters for matrices.
So assume $V = \mathbb C^k$ with the standard complex inner product $\langle \cdot, \cdot \rangle$ w.r.t. to the standard basis $e_1, ..., e_k$. I denote complex conjugation by $\sigma$, and if $A$ is any complex matrix, $\sigma(A)$ means each entry of $A$ gets conjugated.
Setting: Let $f: V \rightarrow V$ be an additive map which is conjugate-linear, i.e. $f(\lambda v) = \sigma(\lambda) f(v)$ for all $\lambda \in \mathbb C, v \in V$, and satisfies $\langle f(v), f(w) \rangle=\langle w, v\rangle$ for all $v,w \in V$.
As you write (in different notation), this means there is a unitary matrix $U \in GL_k(\mathbb C)$ such that for each vector $v = \sum_{i=1}^k a_i e_i$, we have
$$f(v) = U \cdot \pmatrix{\sigma(a_1)\\\vdots\\\sigma(a_k)}.$$
By the way, this is generally how to write $\sigma$-linear maps with matrices w.r.t. a chosen basis. Notice that if $f, g$ are two such $\sigma$-linear operators with matrices $A, B$ to the same basis, then the $\sigma^2$-linear (i.e. linear!) map $f\circ g$ is represented (as a linear map) by the matrix $A \cdot \sigma(B)$.
Anyway, back to your setting.
Proposition: If $f \circ f= id$, then there exists an orthonormal basis $v_1, ,..., v_k$ of $V$ consisting of fixed vectors under $f$, i.e. $f(v_i) = v_i$.
Proof: First, let $0 \neq W$ be any subspace of $V$ that is stable under $f$, and let $0\neq w$. Then either $f(w) = -w$, in which case $iw$ is fixed by $f$; or the vector $f(w)+w \in W$ is $\neq 0$, and by construction fixed by $f$. Either way, we see $W$ contains a nonzero fixed vector $v$ of $f$, and by scaling with the real number $\lVert v \rVert^{-1}$ we can assume it has norm $1$.
Now the assertion follows by induction on the dimension of $V$: For $k=1$ we take $W=V$ and are done; for $k \ge 2$, taking $W=V$ gives us a first normed fixed vector $v_1$, and then we apply the induction hypothesis to $W= v_1^\perp$. QED.
Corollary 1: In our setting, the following are equivalent:
- $f \circ f = id$;
- There is a unitary matrix $B$ such that $B \cdot \sigma(B^{-1}) = U$;
- $U$ is a symmetric matrix.
Proof: $1. \implies 2.$: By the proposition, there exists an orthonormal basis $v_1, ..., v_k$ consisting of fixed vectors for $f$. Let $B = (b_{ij})$ be the base change matrix to that basis, i.e. $v_j = \sum_{i=1}^k b_{ij}e_i$. Because the $v_j$ are orthonormal, $B$ is unitary, and because the $v_j$ are fixed by $f$, we have $B^{-1} \cdot U \cdot \sigma(B) \cdot e_i = e_i$ for all $i$, i.e.
$$B^{-1} \cdot U \cdot \sigma(B) = I_k.$$
$2. \implies 3.$: If $B$ is unitary, $U= B \cdot \sigma(B^{-1})= B \cdot B^T$ which is symmetric.
$3. \implies 1.$: The linear map $f \circ f$ is given by the matrix $U \cdot \sigma(U)$, but $U$ being unitary and symmetric means $\sigma(U)=U^{-1}$. QED.
Let's apply this to our setting, which I interpret as imposing the matrix condition
$$(\ast) \qquad \quad U \cdot \sigma(H) \cdot U^{-1} = H.$$
Note [corrected, thanks!] that is the same as saying $f \circ h \circ f^{-1} = h$ for the map $h$ corresponding to $H$, because the matrix corresponding to $f^{-1}$ is $\sigma^{-1}(U^{-1})$, so that the matrix to the linear map $f \circ h \circ f^{-1}$ is given by $U \cdot \sigma( H \cdot \sigma^{-1}(U^{-1}))$.
Corollary 2: Under the equivalent conditions of Corollary 1, the subset of $\mathfrak{u}_k$ (i.e. all skew-Hermitian ($H = -H^\dagger = -\sigma(H^T)$) complex $k \times k$-matrices $H$) satisfying $(\ast)$ is a real Lie algebra isomorphic to $\mathfrak{so}_k(\mathbb R)$ (i.e. the skew-symmetric real $k \times k$-matrices, i.e. $\mathfrak{su}_k \cap M_n(\mathbb R)$).
Proof: With $B$ as in corollary 1, an isomorphism to $\mathfrak{so}_k(\mathbb R)$ is given by $H \mapsto B^{-1} H B$.
Remarks:
If one imposes condition $(\ast)$ with general (non-symmetric) $U$, in general one gets different subalgebras of $\mathfrak{u}_k$. E.g. $U = \pmatrix{0&-1\\1&0}$ gives out $\mathfrak{su}_2$ which has dimension $3$ and hence is very differnt from the one-dimensional $\mathfrak{so}_2$. I do not know if there are some non-symmetric $U$ which still give out $\mathfrak{so}_k$.
Writing $U$ as $B \cdot \sigma(B^{-1})$ as in Corollary 1 looks very much like an instance of Hilbert 90 to me. However, the other conditions in that corollary show that the setting is actually quite restricted. Still, maybe there is some generalization, with nonabelian Galois cohomology on matrices, which lurks behind this. Or maybe not.