Gliese 581
Your average civ junkie
On normal deity typically around 2200 bc but they can come as early as 2550ish. Then of course there's the special circumstance where a barb kills a unit just outside the borders and there's an improvement within borders one step away they can pillage or a unit one step away that they can attack, they can in this special case enter borders even earlier than otherwise but I think you'll never see a barb inside borders before 2800 regardless of circumstances. Perhaps if it's cornered by expanding culture and unable to move outside borders (not sure).