Given the large distance between the cities, how did they communicate to confirm that the sun was indeed overhead at particular time and date?
They measured something at solar noon. This can be independently measured without communication and only requires to agree on the date. The key, really, was to be able to pick 2 locations on the same longitude and to have enough math/trigo to perform the calculation.
The angle between the sun and the zenith at local solar noon will be the same everywhere at a given latitude so that part doesn't care if the cities are on the same longitude..
You do need to know the north/south distance between the latitudes of the two cities, and picking two cities on the same longitude makes that easier to measure: just go straight from one to the other and note how far you traveled.
If the longitude was substantially different you'd have to use spherical trigonometry to figure out the north/south distance from the distance and bearing of the straight route between the cities, and for that you need to know the size of the sphere you are on.
Instead you'd have to do something like travel north from the southern city until you are at the same latitude as the other city (probably determined by observing the altitude of the North star), note how far you've traveled, then travel east or west along a line of constant latitude to try to reach the other city. If you miss the other city because you didn't get the latitude quite right, you'd have to move north or south, updating your north/south distance estimate, and try again, repeating until you actually hit the other city.