Previous studies of the interior structure of transiting exoplanets have shown that the heavy-element content of gas giants increases with host star metallicity. Since metal-poor planets are less dense and have larger radii than metal-rich planets of the same mass, one might expect that metal-poor stars host a higher proportion of gas giants with large radii than metal-rich stars. Here I present evidence for a negative correlation at the 2.3{sigma} level between eclipse depth and stellar metallicity in the Kepler gas giant candidates. Based on Kendall's {tau} statistics, the probability that eclipse depth depends on star metallicity is 0.981. The correlation is consistent with planets orbiting low-metallicity stars being, on average, larger in comparison with their host stars than planets orbiting metal-rich stars. Furthermore, since metal-rich stars have smaller radii than metal-poor stars of the same mass and age, a uniform population of planets should show a rise in median eclipse depth with [M/H]. The fact that I find the opposite trend indicates that substantial changes in the gas giant interior structure must accompany increasing [M/H]. I investigate whether the known scarcity of giant planets orbiting low-mass stars could masquerade as an eclipse depth-metallicity correlation, given the degeneracy between metallicity and temperature for cool stars in the Kepler Input Catalog. While the eclipse depth-metallicity correlation is not yet on firm statistical footing and will require spectroscopic [Fe/H] measurements for validation, it is an intriguing window into how the interior structure of planets and even the planet formation mechanism may be changing with Galactic chemical evolution.