Complex systems are typically characterized as an intermediate situation between a complete regular structure and a random system. Brain signals can be studied as a striking example of such systems: cortical states can range from highly synchronous and ordered neuronal activity (with higher spiking variability) to desynchronized and disordered regimes (with lower spiking variability). It has been recently shown, by testing independent signatures of criticality, that a phase transition occurs in a cortical state of intermediate spiking variability. Here, we use a symbolic information approach to show that, despite the monotonical increase of the Shannon entropy between ordered and disordered regimes, we can determine an intermediate state of maximum complexity based on the Jensen disequilibrium measure. More specifically, we show that statistical complexity is maximized close to criticality for cortical spiking data of urethane-anesthetized rats, as well as for a network model of excitable elements that presents a critical point of a non-equilibrium phase transition.