Saturation is a relative thing. Astia and E100G would have been considered quite saturated a couple of decades ago.
I have tried to like Provia and can't seem to do so. If I want exaggerated saturation and wild color, Velvia 50 or E100VS. If I want impressive but less exaggerated color and slightly more manageable contrast, it's E100G nowadays. I like Astia for the same sorts of shots, but since I mostly shoot E6 in 35mm and Fuji discontinued it, I've really started to like E100G.
Agreed - why not grab a roll or two of each type and see how they go? When I first shot slides I didn't know what I was doing and 99% of them came out just fine. And when I got my first roll back, I was floored by the colours and the almost three-dimensionality I got in the slides. I never looked back (until I started shooting black and white that is).
My favorite thing is to go where I've never been. D. Arbus
I'd recommend you try them all, but for me, it's Velvia. It was one of the first films I ever shot, and I think it's easier to get right than it seems. It's easy to blow highlights, but apart from that I think it always looks pretty nice. It'll often go a bit purple, but I think for night landscapes, that only adds to it's appeal.
When I used to shoot chromes exclusively it was always Velvia 50, then, later Velvia 100. I'm now slowly getting back into shooting color and have shot a few rolls of Provia and prefer the results to Velvia. Little less saturation, more pleasing colors. Velvia is still great for fall foliage though as someone else mentioned or anytime a "drab" scene needs a kick. But I prefer Provia to Velvia for most subjects.