The magnitude and shape of phenotypic variation depends on properties of the genotype-to-phenotype (GP) map, which itself can evolve over time. The evolution of GP maps is particularly interesting in variable environments, as GP maps can evolve to bias variation in the direction of past selection, increasing the evolvability of the population over time. However, the degree and manner in which environmental variation shapes GP maps and influences evolutionary dynamics may depend on properties of the fitness landscape. To explore how evolutionary dynamics are affected by variable environments across a wide range of different pairs of fitness landscapes, we evolved GP maps to produce spatial-temporal gene expression patterns that matched two-dimensional patterns generated by different elementary cellular automata (CA) rules. We found remarkable variation in how populations evolved in variable environments. In some cases, changing the environment helped populations find higher fitness peaks; in others, it hindered them. The evolution of evolvability also depended on the fitness landscape pair. In some experiments, the ability to generate adaptive phenotypic variation upon environment change increased over time, while in some others, populations found shared areas between fitness landscapes. On the other hand, environmental variability consistently resulted in higher fitness landscape exploration, average fitness and mutational robustness compared to evolution in static environments, which we hypothesize are tightly connected. In conclusion, work presented here sheds light on important general consequences of environmental variability, while also demonstrating dependency on properties of fitness landscapes, which future research on the evolution of evolvability should consider.