The simplest approach is to express the straight-line distance as a function of the curvilinear one, using elementary geometry in the plane of the relevant great circle...
Let's assume Earth to be a perfect sphere of diameter 2R (R=6371 km)
If D is the angular separation between the two cities (i.e., their distance along a great circle is RD, if D is expressed in radians) then their distance in a straight line is:
d = 2R sin(D/2)
For two cities whose (latitude,longitude) coordinates are (A,B) and (A',B') respectively, the SQUARE of sin(D/2) is equal to:
sin^2 ([A-A']/2) cos^2 ([B-B']/2) + sin^2 ([B-B']/2) cos^2([A+A']/2)
Numerically, for Melbourne and Grand Rapids (coordinates in the last two links below) this boils down to:
d = 12036 km (as opposed to the great-circle distance RD = 15621 km)
As shown in the first link below, the difference in the altitudes (195 m and 31 m) of the two cities yields only a tiny adjustment. However, the oblateness of the Earth implies a more significant correction which is somewhere between -28.5 km and +14.3 km (those extremes would correspond respectively to a pair of "cities" located either at the two poles or on two opposite points of the equator).
Actually, the correction due to the oblateness of the Earth is about -7.4 km. All told, the distance between the two cities is precisely 12029.3 km.
See the first link below for the details of that computation, based on the "reference ellipsoid" (IUGG 1980) which is used by geographers to approximate (very well) the actual shape of the Earth.