"Their velocity is constant. So if the distance changes, the frequency of the light must change to keep the speed constant"
Bit what is distance? If you had a ruler it would be warped along with any other matter so you wouldn't see a change in distance.
"so much space has been "created" in the intervening years that they're now microwaves."
But the expansion of the universe "creates" extra space like filling a bathtub with water. Whereas gravity waves surely are more like waves on the water already in the tub.