Graphite is a model system for the study of three-dimensional electrons and holes in the magnetic quantum limit, in which the charges are confined to the lowest Landau levels. We report magneto-transport measurements in pulsed magnetic fields up to 60 T, which resolve the collapse of two charge density wave states hosted by two, electron- and hole-like, Landau levels at 52.3 and 54.2 T respectively. We report evidence for a commensurate charge density wave at 47.1 T in the electron Landau level, and discuss the nature of the density wave instabilities over the full field range, identifying and predicting additional lock-in transitions associated with commensurate density wave states. The theoretical modelling of our results predicts that the ultra-quantum limit is entered above 73.5 T. This state is a bulk insulator, and we discuss its correspondence to the metallic-like transport reported in earlier studies in this field range. We propose that this interaction-induced insulating phase supports surface states that carry no net charge or spin within the planes, but does however support charge transport out of plane. At even higher magnetic fields we eventually expect a topological transition into a quantum spin Hall insulator.