I must say that as much as I love my 16c red, I see that you already have lots of bags in red. simply from perspective of marginal utility, I would say perhaps a beautiful bright blue may do better. The cruise blue did not appeal to me, it's soft and pretty of course, but too muted for me. the bright blue caviar I got had the right shade of bright blue for me, but only avail in chevron caviar. The 16S bright blue is very beautiful and saturated as well (compared to 16C in my opinion) but comes in square mini size only, which was what I have, but I haven't seen it in M/L...
I find that a nice bright blue is hard to find, and a chanel one even harder.. so I would vote for blue for you. I also find that blue does a better job on the surprise pop of color better than red - which is more "expected" as a classic color. On versatility, I find that whatever color clothing you can wear with red, you can wear with bright blue, no?