I have shown that given monic polynomial $$p(t) = t^n + a_{n-1}t^{n-1} + \cdots + a_1t + a_0$$ with companion matrix $$A_p = [e_2 \;|\; e_3 \;|\; \cdots \;|\; e_n \;|\; {\bf a}] \;,\; {\bf a} = (-a_0, -a_1, \ldots, -a_{n-1}),$$ $A_p$ is similar to $A$ if and only if there exists a vector $x$ such that $x, Ax, \ldots, A^{n-1}x$ is a basis for $\mathbb C^n$.
We simply have $$S = [x \;|\; Ax\;|\; \cdots \;|\; A^{n-1}x]$$ and so $A_p = S^{-1}AS \implies A_p$ is similar to $A$.
Now I need to show that
$A_p^T$ is similar to $A_p.$
Does it suffice to say that since $A_p \sim A \implies A^T_p \sim A^T$ and $A^T \sim A$, then $$A^T_p \sim A^T \text{ and } A^T \sim A \text{ and } A \sim A_p \implies A^T_p \sim A_p$$ by the transitive property since similarity is an equivalence relation?
Or is it not okay to use the fact that $A^T \sim A$ since this would immediately give us the result?
Yes, that's a solid argument. It depends on whether you can take $A^T\sim A $ as a given, or you'll have to prove it.