As Samuel said, the Velvia stock is brilliant imho for landscape work. Only thing is, I've found that in certain cases it's difficult to get the whole dynamic range that's captured on the slide into digital without recourse to expensive drum scanning solutions. I've found myself using ND grads to "hold back" skies just to keep the dynamic range within the capabilities of the scanner - the film itself seems to cope at least as well, if not better than my EOS 7D when I examine the slide on the lightbox with a loupe, or when projected.
When I scan slide film, I occasionally have problems that the darker sections of the slide are just not really touched by the scanner, probably the same principle as you get nasty noise on digital shots in the dark bits if you shoot RAW and use recovery to get detail in dark bits. Conversely, with Colour Negative, I seem to get fewer problems with dynamic range, if anything the noisier bits are the light areas - which are dark when scanned, then inverted in software of course. Shooting C41 would be fine, but then you have the problem of colour correction for the orange base of the film - each film being a little different. I've been known to shoot a frame with a colour checker card in frame before taking shots, purely to ease colour correction in lightroom/CS5 at a later date.
Still - Ektar 100 is a nice C41 negative film for landscapes, and worth a punt.
As far as processing goes, for mail-away processing the only lab I've used and been happy enough with the output to recommend is Peak Imaging. Not as cheap as some places, but I've always felt that the output was worth the money.