Maximally random jammed (MRJ) particle packings can be viewed as prototypical glasses in that they are maximally disordered while simultaneously being mechanically rigid. The prediction of the MRJ packing density ϕMRJ, among other packing properties of frictionless particles, still poses many theoretical challenges, even for congruent spheres or disks. Using the geometric-structure approach, we derive for the first time a highly accurate formula for MRJ densities for a very wide class of two-dimensional frictionless packings, namely, binary convex superdisks, with shapes that continuously interpolate between circles and squares. By incorporating specific attributes of MRJ states and a novel organizing principle, our formula yields predictions of ϕMRJ that are in excellent agreement with corresponding computer-simulation estimates in almost the entire α-x plane with semi-axis ratio α and small-particle relative number concentration x. Importantly, in the monodisperse circle limit, the predicted ϕMRJ = 0.834 agrees very well with the very recently numerically discovered MRJ density of 0.827, which distinguishes it from high-density “random-close packing” polycrystalline states and hence provides a stringent test on the theory. Similarly, for non-circular monodisperse superdisks, we predict MRJ states with densities that are appreciably smaller than is conventionally thought to be achievable by standard packing protocols.