Arts for changing a staffs size

Am I right that MuHe is what I am looking for and the base would be 3?

That's correct, as long as it's made from wood and hasn't been shod or bound with metal (as some magi do). Any inlaid gems will be unaffected, so you may need an extra magnitude or a finesse roll (depending on your troupe) not to pop the pretty gems out of the end.

That would basically add a Te requisite, right? But it would work similarly and at a similar magnitude then even bound in metal and inlaid with gems?

Would a Te prereq really be needed, or would simply adding +1 intricacy (or +2) magnitudes suffice? After all, affecting the gems/iron is difficult (by te guidelines), so you would simply use the intricacy magnitudes to ensure the gems/iron are unaffected, either by the growth of the staff or it's changing shape. Perhaps the staff grows only in the sections where there's no pretty gems or metal? Perhaps a Re prereq? Magi with expertise in He and not in Te might prefer this approach.

Is it really so difficult?

I would have thought base is either 3 (slightly unnatural) or 4 (highly unnatural) + 2 (affect metal and gems instead of dirt).

That makes a Terram base of 5 or 10...
Ok, that is way more than Herbam 3...
I should add that the idea was a staff that can be out in a pocket if need be, so partially shrinking is not really an option...

How is that generally handled if an effect is more difficult for a requisite than for a base art? I'd still think the base should be Herbam, it's a wooden staff in the end.

Base 3 MuHe

Adding a prerequisite which is not cosmetic or superfluous adds a magnitude too.

If you go for Range: Touch and Duration: Moon, it will make a level 20 spell.

Pay attention a longer staff may easily be broken by impacts and could be not so practical in rooms and hallways.