Hm the bound for max cut is basically just summing means of hypergeometric distributions, so there's not much intuition to give.

For set cover, it gets more complicated. Because we partition the elements (a la non-overlapping clusters for DP-means), conflicts only happen when the first element of each set is concurrently processed with another element of the same set. That is, the rate of conflict is related to the probability of elements of the same set being concurrently processed. Intuitively, this probability should depend on \tau, but not on the total number of elements.