You need to start with either the Contemporary or the first couple Atlantic Ornette Coleman albums. Actually, on Spotify do a search for The Best of Ornette Coleman, it's a compilation album from the 70s that hits some of the highlights and it's accessible stuff.
The deal with Ornette Coleman's earlier stuff is it was a "piano-less quartet", there was no chordal instrument in the mix. That allowed for more harmonic freedom by the horns as they were just playing over a bass line. To me, those early records sound like a variation on the Charlie Parker bebop stuff, just wackier. The other thing about Coleman is he was a Texas tenor, he played with blues bands and did the gutbucket stuff. He still uses some of the vocabulary in his jazz stuff, which makes for an interesting juxtaposition with the outward-leaning arrangements.
It wasn't until later that he started playing trumpet and violin and things got real nutty for a while.