The presence of strong interactions in a many-body quantum system can lead to a variety of exotic effects. Here we show that even in a comparatively simple setup consisting of a charged impurity in a weakly interacting bosonic medium the competition of length scales gives rise to a highly correlated mesoscopic state. Using quantum Monte Carlo simulations, we unravel its vastly different polaronic properties compared to neutral quantum impurities. Moreover, we identify a transition between the regime amenable to conventional perturbative treatment in the limit of weak atom-ion interactions and a many-body bound state with vanishing quasi-particle residue composed of hundreds of atoms. In order to analyze the structure of the corresponding states, we examine the atom-ion and atom-atom correlation functions which both show nontrivial properties. Our findings are directly relevant to experiments using hybrid atom-ion setups that have recently attained the ultracold regime.