First, some background: the combination of Electric, Ice and Water attacks on a single special sweeper is popular because so few pokémon can resist all three; in fact, only two can, a Volt Absorb Chinchou/Lanturn and Shedinja. All other pokémon take at least standard damage from at least one of those three types.
It bugged me that Shedinja got away with no damage from such an otherwise potent combo, so I decided (as I often do) to research the heck out of the matter. I identified 140 different sets of three attack types, those which are entirely physical or entirely special (since the EV system makes that desirable in Advance Gen) and 89 target types (divided not only by type but also by the Special Abilities that affect type relations. A Hariyama with Thick Fat is a different target type than a Hariyama with Guts.)
I created a scoring system for each set of attack types, as follows:
Each set was given two scores, a Strength score and a Weakness score. A set scores one Strength point for every target type that takes super-effective damage from at least one of the set's types; it scores five Strength points for each target type that takes 4x damage from at least one of the set's types (Shedinja was counted as taking 4x damage from each of the five attack types that hurt it, due to that whole one-hit-point thing.) Obviously, a high Strength score is desirable.
A Weakness score works the opposite way, with low scores being desirable. A set of three attack types scores one Weakness point for every target type that takes, at most, half damage from the set. It scores five Weakness points for every target type that takes, at most, one quarter damage, and it scores ten Weakness points for each target type that it cannot damage at all (mostly Shedinja, but Fighting/Ground/Normal gets a second 10 for Misdreavus and a third for Gengar, ending up with a Weakness score of 30. Ouch!)

Here are the results that I found. I invite folks to discuss the merits of sets that scored well.

First, here's a list of all sets which had a Weakness Score of Zero. Electric/Ice/Water has a Weakness Score of 11 (1 for Volt Absorb Lanturn and 10 for Shedinja.) These sets deal at least standard damage to every pokémon in existance (pre-Diamond/Pearl, that is...)

Bug/Fighting/Ghost
Bug/Ground/Rock
Dark/Dragon/Water
Dark/Electric/Fire
Dragon/Fire/-filler- (Dragon and Fire by themselves cover everything!!)
Flying/Ground/Rock
Fighting/Flying/Ghost
Fighting/Flying/Normal
Fighting/Flying/Poison
Fighting/Flying/Rock
Fighting/Ghost/Ground
Fighting/Ghost/Normal
Fighting/Ghost/Poison
Fighting/Ghost/Rock
Fighting/Ghost/Steel
Fighting/Normal/Rock
Fighting/Rock/Steel
Ghost/Ground/Rock
Ground/Normal/Rock
Ground/Rock/Steel

Second, here are the top twenty Strength Scores. I will italicize, for your convenience, the entries on this list which also were in the previous list.

100 Fire/Grass/Ice
97 Bug/Ground/Rock
94 Flying/Ground/Rock
93 Grass/Ice/Water
91 Bug/Fighting/Rock
91 Electric/Ice/Water
91 Fire/Grass/Water
90 Electric/Grass/Ice
90 Fire/Ice/Water
90 Fighting/Flying/Rock
88 Dark/Grass/Ice
88 Electric/Fire/Water
88 Fighting/Ground/Rock
86 Bug/Flying/Rock
86 Electric/Fire/Grass
86 Electric/Fire/Ice
86 Fighting/Flying/Ground
86 Ghost/Ground/Rock
85 Bug/Flying/Ground
84 Grass/Ice/Psychic

Looks like Bug/Ground/Rock is a highly useful combo...let us all fear Megahorn/Earthquake/Rock Slide Heracross and Nidoking! On the other hand, with the highest Strength Score and a Weakness Score of only 4, this might start people putting Ice Beam on Sunnybeam sets...
Incidentally, since I only explored sets that were entirely special or entirely physical, I cannot speak to the effectiveness of (special)/(special)/Substitute/Focus Punch sets. Does anyone know of such a set that performs as admirably as Bug/Ground/Rock or Fire/Grass/Ice?