Hi Jordan,
I have a guess on how to go looking for it, although the process touches on matters I know little about.
First, let's fix one power $d$, so that the Frobenius action will have eigenvalues of a fixed size. This enables us to compute mod $l$ for large $l$. Then, we should be able to look for an $l$-adic local system $V$ instead of a curve, say of rank $n$. This is because we can reduce $V$ mod $l$ (as usual, by way of compactness of the fundamental group $\pi_1$) to get a sheaf $V_l$. But then, the kernel of the corresponding mod $l$ $\pi_1$-representation will give a curve $f:Y \rightarrow X$. Since $V_l$ trivializes over $Y$, there is an exact sequence
$0 \rightarrow V_l \rightarrow f_*((Z/l)^n) \rightarrow M \rightarrow 0,$
with $M$ just defined as the quotient, so the $q^{d/2}$ part of $H^1(\bar{X}, V_l)$ should inject into $H^1(\bar{Y}, (Z/l)^n)$, giving you what you want.
I admit that several parts of the argument are sloppily written. It seems to me plausible to fix it all up to be rigorous.
Now, where does one get $V$ having $q^{d/2}$ inside $H^1(\bar{X}, V)$? It suffices to have $q^{-d/2}$ as a zero of the $L$-function $L(X,V, t)$. So we go searching for a rank $n$ unramified automorphic form for $K(X)$ whose $L$-function has the right property. This is where my shaky expertise starts to fail, but I've always had the impression that constructing automorphic forms over function fields was a rather accessible combinatorial matter. Perhaps real experts can now comment on whether this is at all plausible.