Who first realized that the shortest distance between two points is a straight line? It's a bit like asking who invented the wheel, but perhaps there's something out there. This seems beyond the obvious crew: Euclid, Pythagoras, etc. Is there any evidence when this became common knowledge.
Subquestion: Same thing but for geodesics.
 A: In order to be a question about mathematics this would have to ask not when the fact became common knowledge -- since it is already known to bees and dogs as mentioned -- but when it got expressed as a theorem.  In fact there was a traditional objection to the whole idea of proof in geometry by people who said common sense was better.  They cited precisely this fact about shortest paths and found it ridiculous to prove a fact known even to asses.  As also noted above, theorems to this effect are about as old as the idea of "theorem" itself, so on one hand the sources are largely lost and on the other hand we should not expect a clear cut answer even if we had all the original sources.
Further, once it becomes mathematics, there is not just one fact about a straight line being the shortest distance.  You have to say shortest among what options.  
Euclid proves a straight line is shorter than any two other straight lines joining the same ends.  He does not offer any more general concept of length of a path.  It might be interesting to know who first announced such a fact for every "path" in the plane, with curves in mind, but you can be sure it was before any clear ideas of continuity or smoothness were known, so it cannot be a very good proof by our standards.  And it was probably made as an unconscious assumption much more often that stated as a fact.
Carlo Beenaker well points out that a major example of geodesics was known to Menelaus of Alexandria. As to distance Menelaus proves analogues of Euclid's theorems such as the side opposite the greatest angle of a (spherical) triangle is the longest.  The rise of the idea of geodesics in general will go notably through Gauss and Riemann, and then the whole idea of "shortest path" gets involved with calculus of variations.  There is a huge amount known of this to historians and no doubt more to be found.  
A: Answering your second question, Menelaus of Alexandria, in his boek Sphaerica, was the first to recognize geodesics on a curved surface as natural analogs of straight lines.
Further reading, here.
