I’m not sure why this was so hard, but Random Colors in AE took way longer then it should have.
I hope this saves someone some time.

I grabbed “Change Color” from the Effects & Presets plane, dropped it onto a Black Solid that I have masked by an image layer. Next I raised the “Lightness” and “Saturation” to where I thought they felt good. Next I oppened “Hue”(

x = number of seconds
f = frames per second
posterizeTime = how many frames to wait before refreshing value
random = any color value between 1° and 360°