Instance optimality is a very interesting property of algorithms. One can generalize notions of instance optimality and come up with surprisingly interesting notions that include worst-case and average-case analysis.
Although it doesn't strictly fall under the purview of traditional algorithm analysis, it is interesting in its own right. The idea in a paper by Afshani-Barbay-Chan (FOCS '09) who discuss a geometric algorithm considers algorithm performance oblivious to input-order (which is relevant to their particular problem).
This might be seen to generalize as follows: For every algorithm partition the inputs into equivalence classes and consider the algorithm performance to be some sort of collective statistic over the average performance for each of these equivalence classes.
Worst-case analysis simply looks at the input as individual equivalence classes and computes the maximum running time. Average case analysis looks at the trivial equivalence class which is a single one comprising all inputs. In the Afshani-Barbay-Chan paper, their algorithm is optimal if the input is partitioned into classes of permutations (i.e., order oblivious performance).
It's not clear if this leads to any new paradigms of algorithm analysis.
Tim Roughgarden's course has some excellent motivating examples and covers different methods to analyse algorithms.