
Roundpole fence
The roundpole fence is the simplest to obtain, but does not succeed in protecting unclaimed ground from your random starving newbie.

Simple stone wall
The simple stone wall would sit between the roundpole fence and the palisade. Makes use of stones, which are readily avaiable even to the newbie, but the construction would be time consuming. It's up to discussion if it should require other materials, like bone glue. Would perform the job of protecting the unclaimed ground of those who still cannot afford yeomanry or leather. As suggest, a dedicated thief with 30+ strenght would put it down with ease.

Palisade
The palisade can still be the all-around mid-tier wall. Requires materials (glue, leather, rope) not hard to find, but that will require the newbie some time to gather. While he searches for the materials/gathers logs/wait for the initial cornerpost to set, the simple stone wall will provide protection.
Citywall/Hard stone wall/Ellaborate wall/Complex wall/Troy wall/Whatever you wanna call it
This wall will stand just before the brickwall. Will require stone, hardened leather, clay, maybe something else that's hard to get but not as hard as metal (bear fur?). Ideal for villages who desire more protection than the palisade can offer but stil weren't able to find metal (like mine, hahahahah).

Brickwall
Stays as the top-tier wall. No changes needed.