One of the main unanswered question of modern Physics is "How does gravity behave at small scales?". The aim of this thesis is to illustrate in a comprehensive but accessible way how to look for deviations from Einstein's theory of General Relativity in this regime, looking at the simplest celestial bodies: static and spherically symmetric ones. With a conservative and bottom-up approach, at smaller scales the first corrections to the action of General Relativity are generally considered to be terms quadratic in the curvature tensors; while these modifications do not cure the inconsistency between gravity and quantum mechanics, the solutions of this theory are plausible candidates to be the first-order corrections of the classical ones. Even with such simple modifications, a striking picture emerges from the study of isolated objects: the unique Schwarzschild solution of General Relativity is only a rare bird in the set of solutions, with non-Schwarzschild black holes, wormholes and naked singularities appearing as possible substitutes. Tailored to graduate students and researchers entering this field, this thesis shows how to construct these new solutions from action principles, how to characterize their metric, how to study their physical properties, such as their stability or Thermodynamics, and how to look for phenomenological signatures.