I'd still rather go with Electric Gardevoir for the Electric STAB, myself. Immunity to paralysis is important to a Pokemon that often lives or dies by its speed, while Poison (The status condition) and Sandstorm immunity rarely matter because most things either switch out on Mega Gardevoir or inflict egregious damage. Wearing it down doesn't generally happen.
Also, here's a replay in which I basically solo a team with Steel Dragonite.
Even though it gets Burned almost at the beginning of the match. http://replay.pokemonshowdown.com/pandora-hiddentype-1110405
Shedinja
First and foremost: Stealth Rock, hurting itself in its Confusion, Nightmare, Curse, Destiny Bond, Perish Song, and Mold Breaker are the only things Shedinja cannot add a type to render itself immune to that normally kill it.
Secondly: there is exactly one reason why Shedinja is sad that it can't add Normal and Fairy: if it is unaffected by Ghost, it
must have added Dark and thus be vulnerable to Fairy, while if it is unaffected by Dark it must have either added Fighting or Dark, and thus be vulnerable to Fairy again. This lack of ambiguity hurts it a little.
Fire: Removes the weakness to Fire, adds a weakness to Water, renders Shedinja immune to Burn. Pretty nice, nothing amazing.
Flying: Immunity to Spikes and Toxic Spikes, adds weaknesses to Electric and Ice, no new resistances. Also makes Shedinja immune to damage from Sky Drop, but that's not much payoff.
Water: Removes the weakness to Fire, adds a weakness to Electric. Eeeh.
Rock: Removes the weakness to Flying and Fire, adds in a weakness to Water and Steel, throws in Sandstorm immunity. Pretty nifty.
Electric: Removes the weakness to Flying, renders it immune to Paralysis. Eeeeh.
Poison: Adds a weakness to Psychic, renders it immune to Toxic and causes it to absorb Toxic Spikes. It may advertise itself explicitly, which is bad.
Steel: Removes the weakness to Flying and Rock, renders it immune to Toxic, Toxic Spikes, and Sandstorm damage, and has no disadvantage. Very nice.
Dark: Removes the weakness to Dark and Ghost, adds a weakness to Fairy. Notable as the only way for Shedinja to remove its Ghost weakness.
Ground: Removes the Rock weakness, adds a Water weakness, renders it immune to Sandstorm damage. A bad Steel, and arguably worse than adding Rock.
Psychic: No advantages, no disadvantages. What's the point?
Dragon: Removes the Fire weakness, adds a weakness to Fairy, Dragon, and Ice. Uh, no.
Ice: Adds a weakness to Steel, renders it immune to Hail. Not as bad as you might expect, but not good either.
Fighting: Removes the weakness to Dark and Rock, adds a weakness to Fairy and Psychic. On the face of it not that good, and hurt by sharing a weakness with Dark, but combined with Safety Goggles it can genuinely confuse your opponent: turn 1, Tyranitar attacks with Rock Slide! Shedinja is not affected, and then is unaffected by the Sandstorm! Your opponent assumes Ground or Steel, and turn 2 attacks with Crunch, and it
also doesn't work. Just being able to completely wall a Tyranitar that lacks Aerial Ace is pretty nice for something that normally hates Tyranitar.
Fairy types
Since you can't add Fairy type to Pokemon in Hidden Type, the first thing I'll cover comprehensively is Fairy-typed Pokemon themselves, since there's no either/or cases of running a Fairy/whatever and adding yadda vs running a whatever/yadda and adding Fairy like you can with other types.
First and foremost, Steel is of course unmatched as an addition for the fact that it covers both of Fairy's weaknesses, giving you a Fairy-typed Pokemon that cannot be counter by Fairy counters per se. For dual-typed Fairies it's not necessarily that clear-cut, however, such as how Carbink and Diancie will remain weak to Steel and weren't weak to Poison in the first place, and now they're weak to Fighting and doubly weak to Ground!
Fairy types
Clefable: Has the movepool to pull off Fairy/Electric, Fairy/Fire, Fairy/Psychic, Fairy/Ice (Don't do it, it's doubly weak to Steel and offensively redundant), Fairy/Bug, and this is just its Special options. Physically it's actually even more diverse, with really good stuff like Drain Punch and Meteor Mash... except it has no good Physical Fairy move. A Fairy/Steel Clefable could still be an interesting mixed attacker, or a good wall if that's the most important thing to you. A Calm Mind Clefable running Stored Power might actually prefer Fairy/Steel to Fairy/Psychic!
Slurpuff: Slurpuff's real problem is that its best stratagem is all-out physical offense while its physical movepool sucks. Since Normal is also impossible to add in this meta, it can't even give itself STAB on Return/Frustration. Special-oriented sets running Calm Mind exist, but they're nothing great. Hidden Type can give those sets a leg up with STAB on Flamethrower or similar, but it's not capable of solving the core problem. Too bad.
Granbull: Adding Dark is the obvious way to go, and Fairy/Dark is actually a quite nice type combination defensively and offensively. A quirky Fairy/Dragon running Outrage is also a possibility, a Fairy/Ground running Earthquake is quite good (Everything that resists Fairy is vulnerable to Ground), it can run Fairy/Fighting quite competently with Close Combat (Not to mention Power Up Punch), it can run any of the Fangs or Punches and Fairy/Fire is actually a quite good type combination... it can even kind of run Fairy/Steel with Iron Tail. Fairy/Rock is also possible, but awful, don't do it. Granbull is quite diverse, and will benefit hugely from the fact that the enemy can't assume you must be one of two or three or just the one possible viable additions.
Florges: The most obvious thing to do is of course to add Grass, making it actually benefit from its own Ability and moves that benefit Grass types. It even has Energy Ball etc. It's also about the only thing it can do of any note, lacking a movepool to do much else. Unfortunate, given that Fairy/Grass is doubly weak to Poison, and this means the primary value of any alternative is to punish the enemy for assuming that it's Fairy/Grass, which itself has the best option being Fairy/Steel, and both of those are Fire vulnerable...
Aromatisse: It can make good use of adding Psychic, and Fairy/Psychic is a good combination in its own right (See: Mega Gardevoir), but it can also pull off Fairy/Electric, which swaps out the Steel weakness for a Ground weakness, or Fairy/Steel running Flash Cannon (Fairy supremacy fighter!), or Fairy/Grass but really go with Florges if you want to do that. It's quite nice, actually.
Sylveon: Honestly, Fairy/Ghost is about as good as it gets for STABs and covers up the Poison weakness in exchange for acquiring a Ghost weakness. It also gets Stored Power, Psyshock, and Synchronoise, but Psychic is a mediocre offensive synergy with Fairy, being a pair walled by Steel 100% reliably. Since you can't add Normal, it can't even run a non-Pixilate version with Moonblast and something like Trump Card.
Xerneas: Dark, Grass, Bug, Rock, Outrage for Dragon for a physical Xerneas. (why) Special Xerneas can add Psychic, Electric, Steel, and also has Grass Knot and Focus Blast. I'd probably go Steel myself and never look back.
Now we're getting into the dual-types, who are much more complicated and interesting. Let's start with by far the most notable one...
Wigglytuff: The only Pokemon in the game (Azurill doesn't count) that has both inaccessible types naturally! Normal/Fairy isn't even that bad of a type combination defensively, since Fairy covers up the Fighting weakness. Between Competitive and a somewhat higher Special Attack, it's probably best off focusing on its Special movepool. Frisk is cool, but not amazing most of the time, and Cute Charm is Garbodor. Nonetheless, it actually has a really really good physical movepool, so don't forget it entirely! As always, adding Electric covers up the Steel weakness, but Wigglytuff has the unique (There's no Ghost/Fairy yet) option of becoming a Normal/Fairy/Ghost, whose only weakness is Steel, and it actually has Shadow Ball too! I would not add Ice, since it brings in its Fighting weakness, makes it doubly weak to Steel, and throws in the Rock weakness too, with of course no real defensive advantage. It can add Psychic, which actually adds no weaknesses while throwing in resistance to Psychic and FIghting, though in exchange you no longer resist Bug and Dark, and of course there's Fire though it has no stand-out advantages in that regard. It also gets Focus Blast, which is notable for breaking through Steel types, but defensively there's no real synergy. Physically it gets all the elemental punches, assorted Fighting moves, Knock Off, Gyro Ball, Wild Charge, Rollout, Power Up Punch... it's diverse. And there's more I can't be bothered to list out too!
Togekiss: Adding Fighting for Aura Sphere is an obvious choice, and it removes the Rock weakness, though it's somewhat awkward gaining a Fairy weakness, Flying weakness and a Psychic weakness, especially given how many Psychic and Flying types can outspeed Togekiss. It can add Psychic for Psychic, with the only downside being a Ghost weakness (You're even still outright resistant to Bug), or it can go Ghost for Shadow Ball to cover up its Poison weakness in exchange for a Ghost weakness but providing some offensive coverage. Fairy/Flying/Fire Togekiss has some potential, though I have to wince at the double weakness to Stealth Rock, but it does remove the Steel and Ice weaknesses and providing offensive coverage for Steel types. It can add Grass, but I wouldn't do that, given that it's a double weakness to Ice and Poison. Lastly, it can add Bug for Signal Beam, which is another double Rock weakness, leaves you severely walled by Steel types (Hi Heatran, particularly Flying Heatran who is triply resistant to Signal Beam), and is just not impressive. Another odd possibility to consider is adding Ground: you would be outright using Hidden Power Ground if you wanted STAB and have a double weakness to Ice, but it removes the weakness to Rock/Stealth Rock, removes the Poison weakness, and replaces a weakness to Electric with immunity, leaving you only weak to Steel and (Doubly) Ice. It's even nearly perfect offensive coverage. (Still walled by Flying Heatran)
Mawile: The obvious thing to do is add Dark for Sucker Punch coverage. It makes you vulnerable to Fighting and covers no weaknesses, but hey, who cares, you super-kill everything with Sucker Punch. It has all the Fangs, but they're all problematic to add STAB to (Double Ground weakness, double Ground weakness, double Ground weakness, and a Fighting/Steel weakness with no advantages whatsoever), it gets several Fighting moves which actually adds no weaknesses but requires you deviate from the Sucker Punch/Iron Head/Play Rough/Swords Dance set, and it's got Rock moves but Steel/Fairy/Rock is adding a weakness to Steel, a weakness to Fighting, a weakness to Water, doubling the weakness to Ground, and for what? You're not vulnerable to Fire, yay? In general, trying to cover up both Fire and Ground weaknesses isn't going anywhere: Grass and Bug both cover up the Ground weakness but in exchange double the Fire weakness, Fire doubles the Ground weakness while covering the Fire weakness (And I already covered Rock), which basically leaves Flying (Adds an Electric weakness but renders you immune to Ground), Water (Which also adds an Electric weakness but covers up the Fire weakness), and Dragon. (Which covers up the Fire weakness with no new weaknesss, actually, basically invalidating Water, and in fact provides resistance to Electric and Water!) Overall I'd probably just add Dark, but Dragon and Flying are better defensive improvements. (Flying in particular makes a switch in on a Ground move completely safe, and Mega Mawile very much appreciates new freedom to switch in, lacking real recovery, not even Leftovers)
Klefki: Basically everything I said about Mawile, only the logic for adding Dark is Foul Play STAB. Also, it lacks the Fangs and any Fighting moves and thus any motivation to run those sub-optimal builds. So, add Dark, Dragon, or Flying, the end?
Azumarill: Adding Ground to a Sap Sipper variant leaves you with no weaknesses! The Huge Power build is overall a lot more powerful, but this is still worth commentary. Alternatively it can run Steel to eliminate the Poison weakness and Grass weakness in exchange for a weakness to Ground, or it can run... not much that appeals. Poison covers up the Poison weakness while adding Psychic and Ground weaknesses, and it has no moves for it, Fighting gives it STAB on some of its moves including Superpower but you add weaknesses to Flying, Psychic, and Fairy without covering up its existing weaknesses... well, Dragon is noteworthy for eliminating the Grass and Electric weaknesses while only adding a Fairy weakness.
Gardevoir: Steel of course trades its Fairy weaknesses for Ground and Fire weaknesses, but it lacks any good STAB to take advantage. Electric swaps the Steel weakness for a Ground weakness and gives it STAB on its Thunderbolts, which can be useful coverage. It might be tempting to add Ghost for STAB Shadow Ball, but it ends up with a double weakness to Ghost. Adding Grass for STAB on Energy Ball would give it a double weakness to Poison, add in Fire, Flying, and Bug weaknesses, and cover up nothing, so avoid that. It could potentially add Fighting for STAB Focus Blast, making it vulnerable to Flying and Fairy and covering no weakness. Eh. There's also adding Bug for STAB Signal Beam, which adds Fire, Flying, and Rock weaknesses without covering up any of its existing weaknesses. Alternatively, focusing entirely on covering its weaknesses, it can add Dark to cover up its weakness to Ghost, gaining a weakness to Fairy and Bug in exchange. Ehhh. It can add Water to cover up its Steel weakness, adding an Electric and Grass weakness. Ow. It can add Fire to cover up its Steel weakness, gaining Water, Rock, and Ground weaknesses, which is just worse than giving it Electric. And it can add Poison to cover up its Poison weakness in exchange for a Ground Weakness. Overall Steel, Poison, and Electric seem its best options, which is somewhat problematic given that they're all weak to Ground. It might be worth adding Flying to your Gardevoir just to mess with people expecting a Ground weakness, for all that it'll add Ice, Rock, and Electric weaknesses without covering its existing ones.
Mr. Mime: Basically what I said about Gardevoir. It even has a similar movepool in regards to STABs!
Whimsicott: Adding Poison reduces it Poison weakness in exchange for a Psychic weakness, which is a decent trade. Adding Steel to eliminate its Poison weakness gives it a double weakness to Fire, though that's actually the only downside. Adding Rock to reduce its Poison weakness gives it a double Steel weakness instead and is just not worth it. Adding Ground to reduce its Poison weakness gives it a double Ice weakness. Adding Ghost to reduce its Poison weakness adds a Ghost weakness, but that's its only downside, and it lets Whimsicott escape entrapment if it cares. Any other type you add will leave it doubly weak to Poison, which is problematic. Ghost, Poison, and Steel all have good points in their favor.
Dedenne: Gosh. Um. It has a terrible movepool, insufficient stats, unimpressive Abilities, and Electric/Fairy doesn't really leap out as having any really awesome synergistic third type to add. If you add Flying it's suddenly weak to Rock and Ice while only covering the Ground weakness, if you add Steel or Poison to cover up the Poison weakness it's doubly weak to Ground, adding Grass makes it doubly weak to Poison, adding Bug removes one weakness while adding two, adding Ground removes the Poison weakness while adding Grass, Water, and Ice... there's just no paths to major improvement.
Diancie: STAB-wise the obvious thing to do is to add Psychic. This adds a weakness to Ghost and does nothing to cover its vulnerabilities. Trying to cover up that tortuous double Steel weakness... Steel will leave it with a double Ground weakness instead. Fire and Electric will also both leave it with a double Ground weakness. Water instead gives it a double Grass weakness. Oh man. Diancie is just screwed. My recommendation: don't use it.
Carbink: Diancie, but with worse stats but good Abilities and a useful movepool. Nothing much to say that I didn't already say with Diancie.