I have experienced issues with grain over the past six months as I traveled around the U.S. and shot a variety of ISO400 films including Tri-X, TMax, HP5+ and Arista. I experimented with different developers including D-76, Ilfosol 3 and HC-110. The reason I was experimenting with different developers was precisely because I was having problems that I never encountered back in Japan where my default developer is Fuji Super Prodol. The first problem I encountered with D-76 was uneven developing. It appeared that not enough developer was getting to the center of the film. So I increased the agitation but then grain became rather pronounced. Like you, I noticed it most often in the sky, especially if I needed to darken the sky in PP. I found that the problem persisted with all of the films and all of the developers, although I was most pleased with HC-110.
But my final conclusion was that while all of those developers require more agitation than Super Prodol, the key is to do sufficient agitation, but not too vigorously. In other words, increase the frequency but keep the agitation gentle. In particular D-76 seems to require more agitation than others to avoid uneven development. Kodak literature suggests very fast agitations; something like one full inversion every second. I find that to be way too vigorous with resulting skies being quite grainy. I try to agitate much more slowly; doing about 4 inversions in ten seconds. (One inversion = 180 degrees two times)
Of course I realize that others may have very different results so this is just my experience. I do all of my developing with stock solution or in the case of HC-110, dilution B.