Added 11/23/12: ChrisJB has given a really wonderful answer that avoids both derivatives and trigonemetric identities by considering geometry not in the (rotated) $xy$ plane but in the (rotated) $v_xv_y$ plane. It took me a while to understand why, in that answer, the distance traveled is proportional to the area of a triangle rather than a trapezoid, so I'm appending below my own original answer a slightly longwinded version of ChrisJB's, for the benefit of others who are as slow as I am. Credit (and upvotes) for it, however, should go entirely to ChrisJB. (You can skip now straight to the bottom.)
Added 11/23/12: This is my longwinded version of ChrisJB's answer.
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$. In the velocity plane, the trajectory starts at $P=(v_0\cos\theta', v_0\sin\theta')$ 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 $-v_0\sin\theta'$. (It's easy enough to work out the $v_x$ coordinates of $Q$ and $P'$, but it's unnecessary to do so.) Denoting points $A=(0,v_0\sin\theta')$ and $A'=(0,-v_0\sin\theta')$ on the $v_y$ axis, we find that the total (downhill) distance traveled by the projectile is proportional to the area of the trapezoid $APP'A'$. (This is because, for a given $\phi$, changes in velocity are proportional to changes in time.) If you draw the trapezoid, it's easy to see that its area is 4 times the area of the triangle $\triangle OPQ$, $O=(0,0)$ being the origin. (This is the "easy to see" point that took me a while to see. If someone with the wherewithal to do so could insert an actual picture here, I would very much appreciate it.) The angle at $Q$ is fixed at $\pi/2 - \phi$ and the length of the side opposite $Q$ is fixed at $OP=v_0$. It doesn't require calculus to conclude that the triangle's area is maximized when $Q$ is the apex of an isosceles triangle, i.e., when $\theta' = \pi/4 + \phi/2$, which translates back to $\theta = \pi/4 - \phi/2$.

