You are using fadeMillis here
if (sunriseMillis - fadeMillis >= fadeInterval){
before setting it to a value. It gets set to a value in sunrise() or sunset(), if you wait a second before the next loop() then is was set over a second ago.
I think you want the writes to the LED pins and the assignment to fadeMillis inside the if statement which checks to see if it is time to fade.
You might need some code restructuring to get the fade happening as soon as the state changes.