So, right now there is a clear progression. Palisade beats fence because it has a higher soak and health. Brick beats palisade because it has a higher soak and health. Adding in new wall types does little to shake things up because the new ones will have a clear cut position. My proposal therefore is lateral movement, accomplished in a variety of ways.
First: Trade offs. Higher material cost for a better wall does nothing. Everyone has materials. Instead, make stat trade offs. A wall that soaks well but shatters due to low health. A wall that is easy to damage but endures for ages. Both I find acceptable effort, but will amount to insufficient. Which means method two.
Second: Stat importance. Right now strength is the only stat that matters for wall breaking. Basically, if there were alternative methods to breaking walls that used different stats, and walls had different soaks for each method. A confusing wall that strength does little against but is vulnerable to psy, for example.
There would, obviously, be different ways to accomplish this, but hopefully we would see variety, security, and an end to whining.