I almost made the same point, but I stopped because I was hesitant to get into the cases where one can do an average-case analysis without assuming any distribu

I almost made the same point, but I stopped because I was hesitant to get into the cases where one can do an average-case analysis without assuming any distributions: when you're doing analysis of a particular operation being called a bunch of times, versus once. In such cases, average-case can yield amortized analysis which still makes no assumption of the input distribution. I'm co-author on a paper which does that: https://www.scott-a-s.com/files/debs2017_daba.pdf https://www.scott-a-s.com/files/debs2017_daba.pdf. In that work, we present a sliding window aggregation algorithm for worst-case constant time, but we compare against ones that are average-case constant time. The average-case constant algorithms are better on throughput, but worst-case constant is better on latency.