[1] For most maps. Gnomic maps (image - http://en.wikipedia.org/wiki/File:Gnomonic_projection_SW.jpg) are designed to show the shortest distance as a straight line. I think the Dymaxion Map aka Fuller Map (image - http://en.wikipedia.org/wiki/File:Dymaxion_map_unfolded.png) is also OK.
You're right. The shortest distance between two points lies on a 'great circle':
https://secure.wikimedia.org/wikipedia/en/wiki/Great_circle
Pun intentional, right? ;-)
[1] For most maps. Gnomic maps (image - http://en.wikipedia.org/wiki/File:Gnomonic_projection_SW.jpg) are designed to show the shortest distance as a straight line. I think the Dymaxion Map aka Fuller Map (image - http://en.wikipedia.org/wiki/File:Dymaxion_map_unfolded.png) is also OK.