Rough terrain with less and less purchase, until it just turns into a pile of dry dust / wet mud (depending on weather). A legged vehicle as heavy as a car would wear away stone, tear roots… I don't think there's any surface that could withstand heavy traffic, except maybe something ridiculous like a fast-growing woody grass.
For some reason, I was imagining a machine with legs like a footstool. Any realistic machine like this would have large, wide feet. With proper suspension, the pressure might be low enough to not completely destroy the ground.
Though, I'm struggling to see how this would be better than a wheeled vehicle: you've still got static friction between the feet and the ground… I guess maybe they're flexing less?
Yeah, large feet would reduce the pressure on the ground, though it would still suffer some effects for sure — but the goal is to avoid rubber and microplastics, so metal feet it is :)
Anyway, I agree that a wheeled vehicle is probably going to win on efficiency just the same, though wheels do require better roads than legs do (eg. common example is stairs).
A bicycle can do stairs just fine. They're tricky, but not much more than a similarly-steep hill would be. (Of course, that's ignoring wear on the tyres from going over the edges of the steps.)