We introduce Riemannian First-Passage Percolation (Riemannian FPP) as a new model of random differential geometry, by considering a random, smooth Riemannian metric on R^d . We are motivated in our study by the random geometry of first-passage percolation (FPP), a lattice model which was developed to model fluid flow through porous media. By adapting techniques from standard FPP, we prove a shape theorem for our model, which says that large balls under this metric converge to a deterministic shape under rescaling. As a consequence, we show that smooth random Riemannian metrics are geodesically complete with probability one.In differential geometry, geodesics are curves which locally minimize length. They need not do so globally: consider great circles on a sphere. For lattice models of FPP, there are many open questions related to minimizing geodesics; similarly, it is interesting from a geometric perspective when geodesics are globally minimizing. In the present study, we show that for any fixed starting direction v, the geodesic starting from the origin in the direction v is not minimizing with probability one. This is a new result which uses the infinitesimal structure of the continuum, and for which there is no equivalent in discrete lattice models of FPP.