So I finally got my barbarian challenge. Note first that I overcrowded a Standard Map (Terra Incognita) with 38 City States, and the standard number of Civs all on the Old World. Even then the savages got to thrive with a few encampments, spawning like rabbits.
During the early game I had hoped to turn the odd Encampment and get a free Brute (who get an awesome bonus when attacking now!), but they kept a worthy challenge by always having a couple Warriors hanging around and constantly threatening my worker inside my dominion. Gladly I didn't lose any of my units (then neither did they get too experienced with Defense XP out), but even when I was fielding three armies I couldn't overrun those troglodytes.
Right after my first setback--losing a warrior--my breakthrough came with a Settler. I managed to use my remaining military to escort him over along the northern coast, and finally he got into the settling spot (and what a spot!) stacked with a bold warrior. But the barbarians had brought in an archer (while I was still building my first), and in a supporting fire flanking operation they broke my defending formation, capturing the settler!
Luckily, his own attacker was now too weakened to keep a tight hold on their newly acquired ransom, so my remaining warrior rescued the settling folks without a pinch. Passing the turn saw an insurmountable fear that they could try a desperate even odds attack at my last warrior, but by now they knew their place.
I settled Hamburg, a city born out of resistance against raging barbarians, and quickly bought lands of Marble and Sheep to keep the greedy Indians out, and the rest is history.
My own Savage Lands: Increased Barbarian Activity
rspeer's Terra Incognita mapscript
zappara's Historic City States
Solver's Hebrew Civilization
Dale's Hardwood strategic resource
p.s. Wish me luck on my 50% roll against the barbarian Encampment!