Do you mean that the resizing step itself introduces grain, or that the sum total of steps from the original introduces grain? If the latter, then is the grain mainly in the darker areas? With digital images, darker areas tend to be grainier than lighter areas, but the grain isn't so visible when they're dark; however, if part of the post-processing is lightening the image, the graininess in the dark areas becomes much more visible when they are lightened. Could that be what you're talking about? If so, there are two ways to reduce it: (1) expose as far to the right as possible, so your dark areas aren't too dark (and hence grainy) to begin with (only possible when the scene's dynamic range isn't too much), or (2) use a tripod to take multiple shots at different exposures, one for the highlights and one for the shadows (which won't be too dark then), and blend them in PS later.
If the graininess is most visible in the sky or other relatively uniform-color regions, one way to make it less visible is to select just that region and then apply a Gaussian Blur filter to smooth out the graininess.
Lisa