Let $A\in M_n(\mathbb{C})$ be a self-adjoint and trace zero matrix.
Let $M_n(\mathbb{C})^1$ be the set of norm one $n\times n$ matrices (with respect to the $L^2\rightarrow L^2$ operator norm).
Consider the set
$$\Phi=\left\{\phi\in M_n(\mathbb{C})^1:\max_{B\in M(\mathbb{C})^1}|\operatorname{Tr(AB)}|=|\operatorname{Tr}(A\phi)|.\right\}.$$
Is it the case that $\Phi$ (for any $n$) always contains an involution ($\phi^2=I_n$) or does there exist an $A$ (and an $n$) such that no entry of $\Phi$ is an involution?
I believe there is always an involution in $\Phi$ when $n=2$.
It's shown that for a self-adjoint $A$ the set $\,\Phi\,$ contains involutions. Your condition "$A$ is traceless" does not come into play.
For arbitrary $A,B\in M_n(\mathbb{C})$ we have $$\operatorname{|Tr}(AB)|\:\le\:\|A\|_1\,\|B\|_\infty\tag{1}$$ where $\|\cdot\|_\infty$ denotes the operator norm, and $$\|A\|_1 = \operatorname{Tr}|A| = \sum_{k=1}^n\sigma_k(A)\tag{2}$$ is the trace-norm, with $\,\sigma\,$ denoting singular values.
Btw, all this remains true in the infinite-dimensional situation.
If $\,V|A|=A\,$ is the polar decomposition, then also $\,V^*V|A|=|A|$. Choose $B=V^*$, then $\|B\|_\infty=1$ (unless $A=0$), and $\:\operatorname{|Tr}(AB)|=\|A\|_1\,$ by cyclicity of the trace. Thus the upper bound in $(1)$ is attained, and we get the value of the max-expression in general $$\max_{B\in M(\mathbb{C})^1}\operatorname{|Tr}(AB)|=\|A\|_1\,.$$
Now let $A$ be self-adjoint:
$A$ is unitarily equivalent to the diagonal matrix $D$ of eigenvalues $\lambda_k(A)$, hence $$\operatorname{Tr}(AB)\; =\;\operatorname{Tr}(DU^*BU)\,,$$ and if $U^*BU=\text{diag}\big(\operatorname{sign}\lambda_1(A),\ldots, \operatorname{sign}\lambda_n(A)\big)$, then $$=\;\operatorname{Tr}|D|\;=\;\|A\|_1$$ Then $B\in\Phi$, and $B$ is involutive, possibly after replacing by $1$ those entries in "diag" corresponding to eigenvalues of $A$ which are zero.