The shortest path between two points on a sphere (and thus with limited applicability also on earth) is a great-circle. I.e.
A great circle is the intersection of the sphere and a plane which passes through the center point of the sphere.
On a sphere, great circles are geodesics. This is the reason why air planes crossing the Atlantic often pass over Iceland. The theoretical proof was given by Bernhard Riemann around 1900.
When did the people that sailed the big oceans started to realise that? Did they realise it at all?
Christopher Columbus always landed in the Caribbean and his path looks as if he wasn't aware of it, but there may be many other reasons for that (winds, passing known islands). Maybe this started only with the beginning of steamboats??
EDIT: @Mike gives an important hint: It depends very much on the maps they used, here is an example of the great-circle from NY to London, in Mercator (upper panel) and Gnomonic (lower panel) projection. In the latter, all straight lines are great circles.