We investigate phase transitions and critical phenomena in Kerr-Newman-Anti de Sitter black holes in the framework of the geometry of their equilibrium thermodynamic state space. The scalar curvature of these state space Riemannian geometries is computed in various ensembles. The scalar curvature diverges at the critical point of second order phase transitions for these systems. Remarkably, however, we show that the state space scalar curvature also carries information about the liquid-gas like first order phase transitions and the consequent instabilities and phase coexistence for these black holes. This is encoded in the turning point behavior and the multi-valued branched structure of the scalar curvature in the neighborhood of these first order phase transitions. We re-examine this first for the conventional Van der Waals system, as a preliminary exercise. Subsequently, we study the Kerr-Newman-AdS black holes for a grand canonical and two mixed ensembles and establish novel phase structures. The state space scalar curvature bears out our assertion for the first order phase transitions for both the known and the new phase structures, and closely resembles the Van der Waals system.