i'm completely befuddled about when and how severely that vassal negative modifier gets applied.
i don't get the impression it's at all related to how the AI feels about the vassal or about the master. when i've been paying attention to it i get a negative from everybody who's not my vassal if i get a negative at all. i read "our rivals" in that context as "other civs". the exception is that your other vassals don't hold it against you. makes sense: DPs work the same way, anybody in a DP with you doesn't resent you for any DPs you have.
in my current game, Gilgamesh created a colony. Louis accepted a voluntary vassal. neither one of them is getting a "-fear our rivals" from any AI. but none of the AIs are friendly towards either of them, or either vassal (most are cautious/pleased, but one AI is annoyed with Louis's vassal). all started out at cautious with Gilga's brand new colony vassal, by definition. i know they do sometimes apply the penalty to each other.
i did a test and created a 2-city colony on an island. i got an instant -2 with everyone. creating a second colony brought the penalty up to -3. creating a third colony was a freebie, the penalty didn't change, still -3. DPs work the same way there too, often it's "buy one, the next is penalty-free". all non-vassal AIs were pleased/friendly with me before the "fear our rivals" negatives, but Louis's vassal is furious (some grudge about taking his 4 best cities). they started at cautious with my colonies of course. my empire is
huge compared with any single AI's empire, even after the colony splits, so maybe they fear my power drastically more than they do each other's?
it makes my brain hurt when i try to sort it all out. often i don't even get a chance to, in a game where i don't go to war or don't take vassals or make colonies. i've watched the penalties more closely in warlords than in BtS.
it may have to do with difficulty, map size, number of civs, game era, and/or the mood of the RNG. it feels like the size of your own empire matters more than map size. game era too maybe, seems like the penalties start out higher when the vassals/colonies are accepted later? but in the gilga/louis example, their vassals are recent so game era hasn't changed, and large empires are more common in later eras so that may just be a side effect of the size thing if it exists. i don't have solid evidence of a darn thing, so i really don't know. but i'd like to.
bonus giggle fact: Louis's new voluntary vassal was B's capitulated vassal earlier (B wasn't getting a "-fear our rivals" back then either"). he broke free from B due to losing more than 50% of his land area, altho he hasn't been in any wars since accepting a master. he didn't have much land left in the first place, and he lost more than half of it due to culture pressure from the cities i captured from him in the war, and the single city his master captured nearby, thanks to the "master gets control of disputed tiles in BFCs" rule.