I'd also recommend Fuji Pro160S or Kodak 160NC. Both have a lot of latitude and very good colors. I'd try them out before your return trip to see which palette you prefer. I've also shot a lot of Velvia over the last 20 years or so, and like it very much for many subjects. I've done extensive close up shooting of flowers in the woods with it, and carry light modifiers to control contrast for it. But I wouldn't recommend it for your subject, as it's on the contrasty side even among slide films.
I'm not sure that split/graduated ND filters would be of that much help in the redwoods, as they won't give you the ability to differentiate between multiple vertical shadowed trunks and lit foliage between them. You need the latitude in the film for this circumstance.
I'd approach it by testing Pro160S and 160NC for latitude and color balance before the trip, and choose whichever gave me the best combination.
If you expect fog, overcast, and low contrast conditions however, Velvia or another slide film of your preference might just give a needed boost, and it's hard to beat Velvia for differentiating various greens.
Lee