I guess I'm having difficulty grasping the concept that the goodness of a state changes depending on how an agent got there
It doesn't.
The value of a state changes depending on what the agent will do next. That is where the dependency on the policy comes in, not in past behaviour, but expectations of future behaviour. The future behaviour depends on the state transitions and rewards presented by the environment, plus it depends on the distribution of actions chosen by the policy.
More formally, the value function of a state is not just a relative and arbitrary scoring system, but equals the expected (discounted) sum of rewards, assuming the MDP follows the given dynamics, including action selection:
$$v_{\pi}(s) = \mathbb{E}_{A \sim \pi}[\sum_{k=0}^\infty \gamma^k R_{t+k+1} | S_t = s]$$
Without identifying a policy, it is not possible to assess a value function. In value-based control methods, the policy to evaluate can be implied, somewhat self-referentially, as the policy that acts greedily (or maybe $\epsilon$-greedily) according to the current estimates of the value function.
If there can be a concrete example (perhaps on a GridWorld or on a chess board), that might make it clear why that might be the case
A very simple deterministic MDP with a start state and two terminal states illustrates this:
Start in state B. Taking the left action is followed by a transition (with $p=1$) to terminal state A, and a reward of $0$. Taking the right action is followed by a transition (with $p=1$) to terminal state C, and a reward of $3$.
What is the value of state B? It depends on what the policy chooses. A deterministic left policy $\pi_1$ has $v_{\pi_1}(B) = 0$, a random policy $\pi_2$ choosing left and right with $p=0.5$ has $v_{\pi_2}(B) = 1.5$. The optimal policy chooses action right always and has $v_{\pi_3}(B) = v^*(B) = 3.0$
