I don't post here much(or at all) but I browse often. Having owned a v500 in the past, I think I can offer some advice.
The V500 likely doesn't have more "real" resolution than 2000SPI. In fact, I found that mine started to get artifacts at anything above 1600-1800SPI. Scanning at a higher res than this will not make the scans better, only give you larger files. You can prove this by making one scan at 2400 and another at 1800. Enlarge the 1800 SPI file to 2400 in photoshop and then compare the two. There should be little to no difference between them, but you may find the lower resolution file is actually sharper!
8x10 from medium format should not be a problem, but from 35mm it's a pretty large enlargement(>8x). As much as you probably don't want to hear it, i'm gonna come across like a scanner snob and say you may want to look into a more capable scanner. I think the v500 is adequate for web res scans, but really falls short for prints. I had a Coolscan before my v500 and the v500 was a huuuuge step down in quality.
Something like a Coolscan 9000 might be more than you'd like to spend, so there are some steps you can take to make sure your scans are as good as they can be. If you want to have a decently clean 2400SPI file, scan at 3600-4800 SPI and downsample the scan to 1800(or 2400) in Photoshop using bicubic. This will reduce scanner noise, particularly with slides. You said negatives, so the effect may not be as noticeable, but it should still help.
Your scans are also gonna need sharpening; my scans from the Epson were very very soft. Only problem, as others said, is that this can make the noise/grain even worse. I'd do some noise reduction to the full res file(3600-4800SPI), then do some high-pass sharpening and then downsample using bicubic, as mentioned above.
I don't remember you saying what film you shoot, but you did mention that the skies are grainy. To reiterate what pellicle said, all the negative film I scan has much grainier blue then all the other colors. If you use Photoshop you can look at the blue channel and see it is noisier/grainier than the rest of the channels. You may want to run some noise reduction on that channel or create a mask and put a small Gaussian blur in areas of smooth light blue tonality(i.e. skies).
The lab may be adding their own sharpening too, and their downsizing may not be that good. I agree with pellicle, you should resize the files yourself before sending them and make sure they aren't doing anything to the files.