IF you have lots of mooks in a fight use average or just take one or two points of damage above or below average as you see fit for the tempo of combat or if it's too easy/hard for PCs.
As for rolling criticals with sneak attack or bucket load of d6/d8 for spells I tend to use only 3 to 4 dices for random factor and take the even number of the rest of the dices and use average.
I.E. if sneak attack crit deals 15d6+6 damage, I roll 3d6+48. you could roll 5d6+41 or 7d6+34 if you want more randomness.
I always roll damage, and in nearly four decades of running games, I have never thought it slowed a game down, or had anyone else comment that they thought so. I find the whole average damage thing rather pointless as a result.