Generalized Threshold-Based Epidemics in Random Graphs: The Power of Extreme Values