The first thing I did was start sleeping predominantly on my sides and stomach, which turns out is how people sleep in nature[1]. This made my apnea all but disappear.
Then after I noticed my sinuses react to dietary changes I went on a carnivore diet -- basically only meat -- for an extended period of time and my sinuses fully cleared up. Right now I deviate from the diet a bit but I remain cautious and it's working out well.
When my breathing improved my clenching subsided.