After listening to a lot of Red's playing, I think what I like most about it is that it all sounds "sung": not just the solos, but also the bass lines and and broken time figures he plays all sound as if they were conceived as sound independent of the theoretical matrix they occur in. Red was a consummate musician who would have been capable of understanding any theory concept, and indeed as a pianist he demonstrated that the finer details of harmony in no way eluded him; at the same time, I think that he also didn't think of jazz as a matrix of rules that must be adhered to, but rather a space to explore in combination with other living, breathing musicians. And to my ears, he didn't seem to mind coloring outside the lines if that's the direction the conversation turned.
But it's the "singing" aspect that I keep returning to in his playing. The thing that I take away from listening to Red's recordings is that I'm always hearing something spontaneous, as if he's searching in the moment all the time for the best sound to play right now in context. Am I projecting? I don't know, but that's what I hear when I listen to him.