Consider what path is traced out by the projectile in the 2d velocity space (horizontal velocity x-axis; horizontal is "after rotating up so the ground is flat, gravity no longer vertical"). It starts somewhere on a circular arc, and thereafter follows a path 'down and to the right' at an angle $\phi$ to the vertical, at constant speed (corresponding to strength of g). Trace the line until it reaches the horizontal. This forms a triangle along with the origin.
The total distance travelled is just (total time in air)x(speed at max height), which is just proportional to the area of the triangle for fixed $\phi$. Possible initial angles give a family of triangles, with one side of fixed length and the opposite angle also fixed ($\pi/2 - \phi$); thus they fit in a circle and the maximum is clearly when the triangle is isosceles.
Added 11/24/2012
Here is a slightly more detailed solution along with a picture. This was written up by Davidac897 with the aid of Barry Cipra's writeup of ChrisJB's solution.
If you rotate the system so the ground is flat, you'll be firing at angle $\theta' = \theta + \phi$ into a medium where gravity points down and to the right at angle $\phi$. Therefore
In the velocity plane, the trajectory starts at $P$ and follows a straight line at angle $\pi/2 - \phi$ to the $v_x$ axis, through a point $Q$ on the $v_x$ axis, down to a point $P'$ with $v_y$ coordinate the negative of that of $P$ (this is true if we fire in a non-rotated frame, and the only difference here is that there is an extra force component in the $x$-direction).
In particular $\angle QOP = \theta' = \theta+\phi$, $\angle PQO = \frac{\pi}{2}-\phi$, and the segments intersect at $R$ in a right angle, where $\overline{QR}$ is the horizontal in the non-rotated frame. Then $OQ$ is the average horizontal speed of the projectile, and $OA$ is proportional to the total time in the area because it is half the total change in vertical velocity. Therefore, the area of the triangle, which is $\frac{(OQ)(OA)}{2}$, is proportional to the total distance traveled.
As remarked above, $OP$ is fixed, as is $\angle PQO$, and the area is maximized when $Q$ is the apex of an isosceles triangle, so $2 \angle QOP + \angle PQO = 2\theta + 2 \phi + \frac{pi}{2}-\phi frac{\pi}{2}-\phi = \pi$, or $$\theta = \frac{\pi}{4}-\frac{\phi}{2}.$$
