From my point of view, the outliner has two basic functions: 1. to organize and find things (objects, lights, mesh data, bones, etc.), and 2. to do stuff to those things (hide/unhide, render/don’t-render, exclude-from-scene/don’t-exclude, etc). Colors themselves don’t change the structural organization of the outliner. Only collections, toggles, and ordering of items does that. So the only thing left for colors to do is to help with finding things and to help with doing stuff to those things.
When it comes to finding things, one consideration is whether the colors help with determining what might be called the scope of a collection - that is, not just what line the collection icon is on, but how big is the collection vertically and how it relates to other collections. This scope can be communicated in two ways.
In the proposal of @nokipaike above, a collection within a collection gets its background colored starting from where the collection checkbox is and going to the right. This allows to see very quickly, just by a quick look at a color, not only how much of the visible outliner belongs to a specific collection, but also to see if that collection is contained within another collection. When it comes to the collection just below the scene collection, he has that collection’s color also extend out leftward to a color bar area, which I don’t think is necessary. If you look at proposal #1 of @natecraddock above, the color bar on the left side just by itself is poor for the task of using colors to actually do things to stuff in the outliner. There is some empty space that one has to track from the location of the left color bar to the collection checkbox(es), and a LOT of empty space to go even further to the toggles on the right of the outliner. Those bars also can not adequately communicate an arbitrarily large number of sub-collections well. So I think that colors bars on the left just are not helpful. I think that @nokipaike includes color to the left of the collection box of the topmost collection under the Scene collection because he wanted the color to connect up to the color bars on the left side, but if those bars are not helpful and are removed, that topmost collection should also have its color go no further left than its own checkbox. If that is done, his proposal captures the scope of particular collections very well, and the horizontal spacing needed for communicating the relations of colored nested collections to other collections is built into the outliner hierarchy.
Further, when it actually comes to doing things to the stuff in the outliner, the fact that the color extends from the outliner items out to the toggle area makes it very easy for the eye to immediately move from the targeted collection or object item in the center of the outliner out towards the toggle that one would use to do something to that collection or object item. So for usability - finding items in the outliner and doing things to those items - I think that a modified version of the proposal of @nokipaike is one of the best out there.
That does not mean that this would be what I would prefer, and I indicated that there is a second option. That second option is to color the collection lines, checkboxes, triangles, and collections names and also to color the toggle icons on the right. Then one can still see the scope of a collection and its relation to other collections, and when one has found the collection that one wants to do something to and thus needs to move the eye to the right towards the toggles, one simply knows that one is looking for the same color as what one just looked at.
Nate objects to coloring the triangle and checkbox on the grounds that “Those are different from the collections themselves”, but there is a one-to-one relationship between a checkbox and a collection. Every time one has a line with a checkbox, one can be assured that there will be a checkbox there, and vice-versa. So in that sense, the checkbox and a collection are not two but one, just as two sides of a coin are both two and yet always one.
The problem, though, is that just coloring the collection icon gives the eye very little color to latch onto. If coloring the vertical line is valuable to point the user to how big the collection is and how it relates to other collections, it too faces the problem that it is still a small sliver of color. Coloring the triangle and checkboxes, in addition to the collection icon and the vertical line, makes it much clearer at a quick glance what color the collection is and how much of the outliner it is taking up.
Look at @dan2’s proposal with the colored checkboxes, triangles, collections icons, and collection text, which does not have the vertical line colored, and it is pretty clear the vertical scope of the collection. Further, if the only two really good choices for communicating vertical scope and for connecting toggles on the right to the center of the outliner is a modified version of the proposal of @nokipaike or the proposal of @dan2, the proposal of @dan2 has much less visual noise and clutter, coloring just small icons already there than changing most of the background to various different colors. It is in light of this that I would sincerely hope that Nate reconsiders his objection to coloring the triangles and checkboxes. It (or something close to it) seems to be the best option for making it easy to find items and to do things to them with the least visual clutter.
)