Does every non-trivial finite group have a subgroup with prime index?

No. The first counterexample I can think of is $A_8$. The largest prime factor of $|A_8|$ is seven. But if there were a subgroup $H$ of index $p\le7$, then there would also be a non-trivial homomorphism $\phi:A_8\to S_p$. More precisely, the natural action of $A_8$ on the collection $X=A_8/H$ of left cosets of $H$ given by the rule $g\cdot (xH)=(gx)H$ is a homomorphism from $A_8$ to $Sym(X)\simeq S_p$. Because the action is transitive, the homomorphism is not trivial.

But because $|S_p|\le |S_7|<|A_8|$, $\operatorname{Ker}(\phi)\unlhd A_8$ is necessarily a non-trivial normal subgroup contradicting simplicity of $A_8$.

This article is relevant.

In it, Robert Guralnick classifies - using the classification - the finite simple groups that have a subgroup of prime-power index.

---

Added The case of solvable groups.

If $G$ is a solvable groups, then $G' < G$, where $G'$ is the derived subgroup. Now $G/G'$ is an abelian group. Find a subgroup $H/G'$ of prime index in it, and pull it back to a subgroup of prime index $H$ in $G$.

$A_n$ , has no subgroup of prime index iff $n \geq 6$ and $n$ is not prime .

Because of this theorm :
Theorem : If $G$ is a simple group with subgroup of index $m>1$, then $$|G|\quad |\quad m!$$ Proof : if $G$ has subgroup $H$ , and $G$ act on the cosets of $H$, then we have homomorphism from $G$ to $S_m$ with trivial kernel (because $G$ is simple).
Of course $A_{p-1} \triangleleft A_p$ .$\Box$

For another examples , because only normal subgroups of $S_n ( n \geq 5)$ are $ 1 , A_n $and $S_n$, by the same way you can show there is no subgroup of index $2<r<n$ in $S_n$ .