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 of $\pi/2 + \phi$ at $O$.
Rhombus http://cs.smith.edu/~orourke/MathOverflow/ProjectileCipra.jpg
(Figure added by J.O'Rourke)
Added later: At the risk of complicating things, let me explain why $T=2u/g$.
Decompose the downhill vector $W$ into its horizontal and vertical components, writing $W=X-Y$, with components of (positive) length $x$ and $y$, respectively. (Note: the variables here denote velocities and speeds, not positions!) From the (absent, but easily drawn) picture, we have $\tan\phi = y/x$. Now, in addition to the projectile $P$ fired with initial velocity $V=U+W = U+X-Y$, imagine we fire two virtual projectiles: projectile $A$ straight up with velocity $U$ and projectile $B$ up and out with velocity $U+X$.
Because they have the same vertical component of velocity, $A$ and $B$ will always be at the same height; they simply separate horizontally with speed $x$. Similarly, $B$ and $P$, which have the same horizontal component of velocity, will always be vertically aligned, separating vertically at speed $y$. Gravity plays no role in the size, shape, or orientation of the triangle $\triangle ABP$; at any time $t$, it is a right triangle with a horizontal leg of length $|AB| = xt$ and vertical leg of length $|BP|=yt$. Hence the angle at $A$ is $\phi$, since the tangent is $yt/xt = y/x = \tan\phi$. This means that $AP$ is always parallel to the downhill slope, which means that projectiles $A$ and $P$ will hit the ground simultaneously.
But it's quite clear that $A$, being fired straight up with initial speed $u$, will land after time $T=2u/g$: It takes gravity time $u/g$ to bring the projectile to rest, and the same amount of time to bring it back down.