The properties of mobile impurities in quantum magnets are fundamental for our understanding of strongly correlated materials and may play a key role in the physics of high-temperature superconductivity. Hereby, the motion of hole-like defects through an antiferromagnet has been of particular importance. It creates magnetic frustrations that lead to the formation of a quasiparticle, whose complex structure continues to pose substantial challenges to theory and numerical simulations. In this article, we develop a non-perturbative theoretical approach to describe the microscopic properties of such magnetic polarons. Based on the self-consistent Born approximation, which is provenly accurate in the strong-coupling regime, we obtain a complete description of the polaron wave function by solving a set of Dyson-like equations that permit to compute relevant spin-hole correlation functions. We apply this new method to analyze the spatial structure of magnetic polarons in the strongly interacting regime and find qualitative differences from predictions of previously applied truncation schemes. Our calculations reveal a remarkably high spatial symmetry of the polaronic magnetization cloud and a surprising misalignment between its orientation and the polaron crystal momentum. The developed framework opens up a new approach to the microscopic properties of doped quantum magnets and will enable detailed analyses of ongoing experiments based on cold-atom quantum simulations of the Fermi-Hubbard model.