Thanks very much to @whuber for the initial answer. thought I should upload the results of me doing much the same...
For what its worth the particular form of MDS that I used is something called t-SNE (aka 't-distributed Stochastic Neihbor Embedding') to achieve the following images.
Here's a picture of all the cities in order - on the left axis is the actual 1-d location for that city, and the cities arranged in order from top to bottom, left to right across that axis.. color = country
Here's another picture where I took the line of cities but plotted it on the world map.. I guess bottom line this problem reduces to something pretty close to the traveling sales person problem - but with the difference that its not just an ordering of cities but a mapping of cities to a 1-d line...
If anyone wants the full output data or methodology used here, please message me.
In response to @whuber's commment..
Yes you are right when you emphasize local distance (that is that local distances of immediate neighbours should be as close as possible to actual distances on the world map) the MDS problem reduces to the travelling salesman problem. However if you emphasize the optimizing (or matching) of distances over a wider/more moderate range you can get different results. For example here's what the the t-sne algorithm gives when you use a higher value for 'perplexity':