Dancing Hoskuld
Deity
That's it. The speed bonus is Woodsman 2. I guess the other option is to make the not get any defensive bonuses, but they would still be deadly on open ground, and it wouldn't make any sense. I think Neandethals should be dangerous, but that you should be able to kill them with a one two punch by sacrificing a unit and finishing them off with another. Right now that's not workable until you get str 3 units (and even then it's hard).
Just added Sabretooth Tigers to make life even harder. If you activate them.