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.)
Here's something that at least avoids taking derivatives.
Let's start with a warm-up on flat ground. If you fire a projectile with vertical velocity $v_y$ and horizontal velocity $v_x$, the amount of time it spends in the air is $T=2v_y/g$ and the distance it travels is $D=v_xT$. As a function of firing angle $\theta$, we have $v_y=v_0\sin\theta$ and $v_x=v_0\cos\theta$. Setting $v_0=g=1$ to clean out the clutter, we have
$$D=2\sin\theta\cos\theta = \sin(2\theta),$$
which is clearly maximized, taking the value $1$, when $\theta = \pi/4$.
Now suppose the ground slopes down at angle $\phi$. Let's rotate it up flat, and imagine firing at angle $\theta' = \theta + \phi$. (We're not taking derivatives, so there should be no confusion in using the notation $\theta'$.) The obvious problem is, gravity no longer points straight down. Instead it has a vertical component $g_y = g\cos\phi$, pointing down, and a horizontal component $g_x = g\sin\phi$, pointing to the right. In terms of their effect, the vertical component $g_y$ is a new (and reduced) gravity, while the horizontal component $g_x$ acts as a kind of additional magnetic force on the projectile, accelerating it in the $x$ direction. Thus the amount of time a projectile fired with vertical velocity $v_y$ spends in the air is $T=2v_y/g_y$, much as before, while the horizontal (actually downhill) distance it travels is now
$$D = v_xT + {1\over2}g_xT^2 = 2v_y(v_xg_y + v_yg_x)/g_y^2.$$
We have $v_y = v_0\cos\theta'$ and $v_x = v_0\sin\theta'$. In this case it's convenient to adopt the clutter-cleaning convention $v_0 = \cos\phi$, which leaves us with
$$D=2\sin\theta'(\cos\theta'\cos\phi + \sin\theta'\sin\phi)=2\sin\theta'\cos(\theta'-\phi),$$
using the angle addition formula $\cos(x-y) = \cos x \cos y + \sin x \sin y$. The formula $2\sin x\cos y = \sin(x+y)+\sin(x-y)$ turns this into
$$D = \sin(2\theta'-\phi) + \sin\phi = \sin(2\theta + \phi) + \sin\phi,$$
which this time is maximized, taking the value $1+\sin\phi$, when $2\theta+\phi = \pi/2$, which is to say, when $\theta = \pi/4 - \phi/2$.
Added 11/15/12: Oops, I just fixed a minor mistake: the correct clutter-cleaning convention is $v_0 = \cos\phi$, not $\sin\phi$. I should have realized this right away from the fact that it needs to agree with the flat-ground convention, $v_0=1$, when $\phi=0$. (I had elsewhere kept my sines and cosines straight using, for example, the fact that $g_x$ should be negligible for $\phi\approx0$.) The full factor in $D$ that begs to be set equal to $1$ is $v_0^2/g\cos^2\phi$. If you stick with the convention $v_0=g=1$, you find that the maximum downhill distance, as a function of $\phi$ is
$$D_\max = \sec^2\phi+\sec\phi\tan\phi,$$
whose horizontal component is
$$H_\max = D_\max \cos\phi = \sec\phi + \tan\phi.$$
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$.