Haven't really seen any change to barbs this new patch (normally play on Prince or King)
From experience, it's actually not a matter of difficulty level, as it is your start location. There are some start locations where barbs can be more difficult on Prince than Deity, especially if multiple camps have horsemen. If anything, Barbs can actually helon higher difficulties because they capture AI settlers (AI will have more on higher difficulties) and ship them right at you. Kinda silly....Of course, being set back a little on deity is bigger deal than being set back a lot of Prince-
Starts that are sparse tend to have worse barbarian issues, as there's more places for barb camps. The other thing is your promximity to other City States and civs. For example, if you spawn near 2 city states, they will generally hold off barbs from that direction for you, while if your location has no city states, then expect barb stupidity.
Honestly, I think Barbarian problems come in a few layers.
1. ) Horsemen are too strong even with the fact they have less strength early on; the mobility is highly unfair-- you're basically under attack by a weaker version of Scythia from turn 1. These need to come much later. Personally, I think they should be removed completely, as there's too much of a distortion.
2.) What can you do to stop a barb scout that arrives at turn 2? Nothing. Barb scouts should be easier to kill? They usually take a few hits to kill, and even with the +5 card is hard to catch them.
3.) Related to no.1, why do Barbarians keep up with people in tech? You will see them running around with muskets when sometimes the AI doesn't even have them. IMO, they need to be made less advanced. Civ IV usually put a cap on their advancement with free spawns and forced them to build more advanced units and founding their own cities. So you could see them with advanced units, but they had to actually earn them. And while not Barbarians, the fact that city rebels can spawn more advanced units than anyone was using is just dumb as well. And it is just as stupid to see battleships come out of a hut.
4.) I also think civs should receive an inherent bonus against barbs too. You can reduce or remove it on higher levels.
Finally, to those that need help dealing with barbs, warriors are generally pretty solid on