Fluctuating environments are situations where the spatio-temporal stochasticity plays a significant role in the evolutionary dynamics. The study of the evolution of cooperation in these environments typically assumes a homogeneous, well mixed population, whose constituents are endowed with identical capabilities. In this paper, we generalize these results by developing a systematic study for the cooperation dynamics in fluctuating environments under the consideration of structured, heterogeneous populations with individual entities subjected to general behavioral rules. Considering complex network topologies, and a behavioral rule based on generalized reciprocity, we perform a detailed analysis of the effect of the underlying interaction structure on the evolutionary stability of cooperation. We find that, in the presence of environmental fluctuations, the cooperation dynamics can lead to the creation of multiple network components, each with distinct evolutionary properties. This is paralleled to the freezing state in the Random Energy Model. We utilize this result to examine the applicability of our generalized reciprocity behavioral rule in a variety of settings. We thereby show that the introduced rule leads to steady state cooperative behavior that is always greater than or equal to the one predicted by the evolutionary stability analysis of unconditional cooperation. As a consequence, the implementation of our results may go beyond explaining the evolution of cooperation. In particular, they can be directly applied in domains that deal with the development of artificial systems able to adequately mimic reality, such as reinforcement learning.