Carracosta - Solid Rock + Sturdy + Swift Swim (just try to stop this guy from setting up)
Gorebyss - Swift Swim + Hydration (only fully evolved mon with this combo, and Shell Smash to boot)
Heatran - Flash Fire + Flame Body (small, but Flame Body is a great defensive ability that saw little use due to Flash Fire)
Mamoswine - Oblivious + Snow Cloak + Thick Fat (easily the best Snow Cloak abuser)
Miltank - Thick Fat + Scrappy + Sap Sipper (Fire and Ice resists + Grass immunity + near perfect coverage with Scrappy)
Octilerry - Suction Cups + Sniper + Moody (immune to phazing and boosts with Moody and Sniper Focus Energy)
Snorlax - Immunity + Thick Fat + Gluttony (no longer needs to choose between poison immunity and resistances, and indeed wants to be poisoned for status immunity)
Walrein - Thick Fat + Ice Body + Oblivious (Fire resist, practically Ice immune, Tauntproof, and permahail is back)
On the topic of Oblivious, Infatuation is now a real thing to watch out for now with Cute Charm becoming standard on many mons (including premier staller Clefable). Indeed, this combined with Rivalry makes Gender in general much more relevant.