Here's another solution, which is certainly simpler than the first one I gave, and may also be simpler than ChrisJB's.  It would again benefit from a drawing, but I hope the verbal description will suffice.

Let $V$ denote the (initial) velocity vector (of length $v_0$), and write $V=U+W$, where $U$ points in the "up" direction and $W$ points in the "downhill" direction.  Together with the origin $O$, we have a parallelogram $OUVW$, with angle $\pi/2 + \phi$ at $O$.  Let $u$ and $w$ be the lengths of $U$ and $W$.

The trick is to realize that the amount of time the projectile spends in the air is simply $T=2u/g$.  Consequently, the downhill distance it travels is $D=wT=2uw/g$.  The variable quantity here, $uw$, is proportional to the area of the parallelogram $OUVW$, which has fixed angles and a diagonal ($OV$) of fixed length.  This area, and hence the distance $D$, is maximized when the parallogram is a rhombus, which is to say when $OV$ bisects the angle at $\pi/2 + \phi$ at $O$.