I'm trying to think of a counter-example to the perpendicular line thing, but it seems pretty good at the moment (assuming the functions are well-behaved). You can find the equation of the normal as a function of x1, and the maxima/minima will occur when this normal is perpendicular to the gradient of the other line at the point of intersection.
And the two methods I used both involve partial derivatives, which are not part of specialist. I shall leave them for later. 
Because you mentioned partial derivatives, I looked them up and they have spiked my interest xD.
You are doing exactly as I was doing - I just don't understand why it will ALWAYS be a perpendicular line to one of the curves... If it is always the case, is there a mathematical method of proving it?
Any help on this issue would be splendid.
EDIT: I just saw Thushan's post, and the whole idea of perpendicular lines is beginning to make more sense to me - Thanks Thushan, Brightsky and Mao -> You're all legends 
Partial differentiation, as you would have worked it out, is just differentiating against one variable while holding another variable constant. The method is simple, though there are quite a bit of theory in multivariable about it (i.e. partial derivative is different to total derivative/material derivative, etc). In our case, we make the assumption that our two variables are both
independent variables, thus partial differentiation is justified.
The square of the distance function be defined as
 = (f(x_1)-g(x_2))^2 + (x_1-x_2)^2)
We require a minimum or maximum distance, thus we find:
 & = 0 \\<br />\implies (f(x_1) - g(x_2))f'(x_1) + (x_1-x_2) & = 0 \\<br />\partial_{x_2} D^2(x_1,x_2) & = 0 \\<br />\implies (f(x_1) - g(x_2))g'(x_2) + (x_1-x_2) & = 0 \\<br />\end{align*}<br />)
Solving the above would give us x1 and x2, the x coordinates of points on the two functions that give minimum/maximum distance.
We postulate that the line joining these two points must be orthogonal to both lines. The gradient of this line is
-g(x_2)}{x_1-x_2})
, thus it must satisfy:
 & = -1 \\<br />\implies (f(x_1)-g(x_2))f'(x_1) + (x_1-x_2) & = 0 \\<br />m \cdot g'(x_2) & = -1 \\<br />\implies (f(x_1)-g(x_2))g'(x_2) + (x_1-x_2) & = 0 \\<br />\end{align*})
These two equations are exactly the same as the partial differentiation method. Thus the postulate above is proven to be true.
One algorithm for solving using the 'orthogonal to both graphs' is:
1. Find the normal of
)
at any

, you should arrive at
} + f(x_1))
2. Find the intersection of this normal to
)
, that is, solve
 = -\frac{x_2 -x_1}{f'(x_1)} + f(x_1))
for

in terms of

3. Find

such that
 = f'(x_1))
, that is, substitute the expression for

from above into
)
to express the LHS in terms of

, then solve the equation for
