The short answer is yes.
(For purposes of this discussion, I am using a two-dimensional approximation. The mathematics is more complex, but the principle the same, if it is done with consideration of the curved surface of the earth included. References to a straight line should then be read as a great circle, which is the shortest distance between any two points on a sphere. I am also treating each city as a point, not an extended area.)
If the three cities do not all lie on the same line, they can be considered to form the three vertices of a triangle. Any triangle has a point, called the circumcenter, which is equidistant from the three vertices.
Since the technique used to find the circumcenter involves constructing the perpendicular bisector of the line between any two pairs of the points, and seeing where those two lines intersect, it won't work when the three points all lie on the same straight line. The two perpendicular bisectors will be parallel to each other, so they will never meet. If we are considering the surface as a flat plane, then there will be no point that is equidistant from all three.
Edited to correct this: On a sphere, the 'perpendicular bisectors' can indeed intersect. If you picture three points in the equator, then the North Pole (or South Pole) will be equidistant from them all, as that distance is simply a quarter of the Earth's diameter. A similar construction can be made for any three collinear points. So, since the earth is spherical (more or less) rather than flat, the answer is YES - there will always be a point somewhere on the surface of the earth which is equidistant from all three cities.