The spawning is random, but Barbarian AI isn't completely random: if I remember correctly, it executes an AI warplan just like any other AI race, which targets one specific civ at a time. Every X turns it switches to a new civ, weighted towards higher scores. To see this in action, put on raging barbs and boost your score in WB. Wait till you have a steady stream of barbs and then go into WB again and have a look at barbarian movements: you'll see they are even moving through other AI's territory, ignoring their cities, to get to you.
The Horsemen use AI warplan just like any other barb, so even if they spawn far away, if you're the current target they'll walk halfway across the world to get you. However, because they have such high movement, they'll often get sidelined with 'targets of opportunity': IIRC AI will prioritise very weakly defended cities and workers above their set AI routine. You can actually abuse this in-game by moving workers away from your cities as bait if you need to buy a turn or two.