When Hartle discusses the geodesics in his Gravity: An Introduction to Einstein's General Relativity book he uses the following definition for the Lagrangian:
$ L \Big(\frac{d x^\alpha}{d \sigma}, x^\alpha \Big)=\Big(-g_{\alpha\beta}(x) \frac{d x^\alpha}{d \sigma} \frac{d x^\beta}{d \sigma} \Big)^{1/2}$
where $\sigma$ is used to parameterize the path of a massive point particle. Where does this definition come from?
The corresponding action $S=\int_{\sigma_i}^{\sigma_f} \mathrm{d}\sigma~L$ is the arc length between 2 spacetime events. The principle of stationary action (with Dirichlet boundary conditions) therefore leads to geodesics.
See also e.g. this related Phys.SE post.
Hartle's Lagrangian is designed so that the corresponding Euler-Lagrange equation coincides with the geodesic equation for the metric $g_{\alpha\beta}$. That this is so is a standard exercise with Christoffel symbols that appears in most GR books.
This is a good question, and there are probably technicalities that I'm not quite qualified to address. I'll give a non-rigorous answer and try to avoid any absolute statements.
Geodesics are defined abstractly on some manifold, but they are a direct generalization of the idea of a straight line. Note that in a flat space a straight line is the "shortest path between two points". In many cases the geodesic is the "shortest proper time between two points" generalizing the idea of a straight line to curved minkowski space (many cases meaning every case I know of, but there are probably some examples where this does not exactly hold).
The proper time between two points is the integral (playing fast and loose with differentials), $$S = \int_{\sigma_0}^{\sigma_1}ds = \int\sqrt{\frac{dt}{d\sigma}^2 - \frac{d\textbf{x}}{d\sigma}^2}d\sigma=\int\sqrt{-g_{\alpha\beta}\frac{dx^\alpha}{d\sigma}\frac{dx^\beta}{d\sigma}}d\sigma$$ Then if a geodesic minimizes this, you can take as your langrangian $\mathcal{L} = \sqrt{-g_{\alpha\beta}\frac{dx^\alpha}{d\sigma}\frac{dx^\beta}{d\sigma}}$ and apply the Euler Lagrange equations to minimize it. Usually to call this an "action" it needs to have units of energy, so it is multiplied by mass. There are also overall minus signs that depend on the signature used (I might have messed these up).
Many people first encounter geodesics in the context of airplane routes, where the geodesic (path of minimum distance) is to travel on the "great circle" connecting the two points. This is the same principle.
