Found Gesualdo on my mind tonight and listening to him now, his music is so divine. I can't help thinking about space, the "heavens" and a lot of existential stuff with his music, there's a profundity not too unlike Stockhausen's mid-late works.
I'll probably already know some of your suggestions but what do you recommend as far as unpredictable, chromatic and majestic early music?
I've been asked this question before by someone who loved Gesualdo's most chromatic music, and it's really hard to answer just because Gesualdo in that mode is a sort of extreme case. You could listen to madrigals by Luca Marenzio and the earlier books of madrigals by Monteverdi, but they aren't as shocking as Gesualdo (though I have to say that I enjoy Marenzio and Monteverdi more than Gesualdo.)
One line worth exploring is the movement called Ars Subtilior, if you search it in this forum you'll see a certain amount of discussion. Composers like Solages. This music was experimental both rhythmically and harmonically, and in a decent performance you should hear the same sense of pushing boundaries that you hear in some Gesualdo.
If you want to check early instrumental music which explores chromaticism, let me know and I'll think about it.