Making bad Pokémon better is something I've been interested in, and I kind of thought of doing something like this by myself. So, I'll put my ideas here, while following a few of my own rules.
Ninjask [Optimized]
Abilities: Speed Boost | [HA] Infiltrator
Stats: 73 HP / 110 Atk / 45 Def / 50 SpA / 75 SpD / 160 Spe
Added Moves: Shadow Sneak, Shadow Claw, Sky Attack, Acrobatics, Tailwind, Lunge, Quick Attack, Teleport, Fly, Smokescreen
Summary of Changes: +12 HP, +20 Atk, +25 SpD
Ninjask is frail Defensively, but with it being a Bug-type, this is justified. Ninjask also has a double weakness to Stealth Rock, so it's impossible to switch to, except for a Grass or Fighting-type attack. With Ninjask's Speed, Lunge can weaken a Physical attacker and make it possible to survive their attack. Honestly, Ninjask could be best as a Physical sweeper itself with an update to its Physical pool and a bit more Attack. Ninja are pretty sneaky, thus Shadow Sneak. Ninjask also gets Shadow Claw for another claw-based attack. This one will at least let Ninjask damage Steel-types normally, whereas Dig and Night Slash were its only options before. Acrobatics can be used alongside a Focus Sash, or a Power Herb with Sky Attack.
Shedinja [Optimized]
Abilities: Wonder Guard (Now protects Shedinja from any type of damage other than burns and super effective moves, and Z-Moves.)
Stats: 1 HP / 110 Atk / 45 Def / 65 SpA / 75 SpD / 130 Spe
Added Moves: Roost (haha), Fly, Thunder Wave, Swords Dance, U-turn, Destiny Bond, Trick Room, Defog, Psychic
Summary of Changes: +20 Atk, +35 SpA, +45 SpD, +90 Spe
Not that there's any point in boosting Shedinja's Special Defense.
Wonder Guard gets a huge boost that makes it as almost as wonderful as possible. No more instant KO by Stealth Rocks/Spikes and poison. Shedinja becomes the ultimate switch-in, immune to nearly anything. This even includes recoil and crash damage. However, being weak to Fire makes it still susceptible to burns.
It's still pretty ninja-y, so why not give it high Speed? Its new Speed lets it get off a Thunder Wave or a Will-o-Wisp on a super effective attacker before they actually attack and KO Shedinja. It can switch into an attack it's immune to, Swords Dance the next turn, and U-turn the opponent's switch the turn after that. It can also reliably use Destiny Bond when it knows it's about to faint.