I liked the Zelda / Sheik gimmick a lot to. In Melee. Where it made a lot of sence to me. But then I learned how badly balanced Zelda was. Not that I was good with either at that point (nowadays, I'm a pretty decent Sheik, but that's mostly cause I watched so many Melee top players play, and found out Sheik fitted me more than Fox / Falco / Marth). And I don't really see how they should also remove the Pokémon Trainer, Ice Climbers or Zero Suit Samus if they'd cut Sheik. Those characters also have problems (quite a lot of them even), sure. But for a whole different bunch of reasons than Zelda / Sheik altogether.
To put it another way, there's just as much reason to cut those as there is Sheik. Ice Climbers are no longer relevant, their gimmick is not a good thing anymore or causing Sakurai trouble. Same with Pokemon Trainer. Zero Suit Samus clearly is better than Samus, so cutting her means Samus won't entirely suck. Basically, the reasons amount to the same crap right now. None worth noting. However, the extra models onscreen are specific to Ice Climbers and Pokemon Trainer and they could actually get cut because of that.
And Tingle might be more well known than Impa perhaps, and has had actual roles in Smash before as a stage obstacle of sorts in Melee, and an Assist Trophy in Brawl. But I think I explained it before already how that goes. Impa didn't had a trophy nor sticker in Melee or Brawl, but I don't think she'd be overlooked at all. Brawl's Zelda trophies where all from Twilight Princess and Wind Waker mostly (model rips and all), and in Melee, it was mostly Majora's Mask for whatever reason. It's perhaps notable that none of the other Sages from Ocarina of Time got a trophy either. And of coarse the fact that Impa had quite drastic different looks from Ocarina of Time to the Oracle games. Plus, her Skyward Sword appearance really made the character.
I can understand in Brawl her not having an appearance since there was no relevant image to go off of. But Ocarina of Time was also well repped with Trophies/Songs in Melee so I don't buy that. Sakurai just didn't know of her, and as of right now, he probably doesn't care enough to make her playable. Also, he clearly fully knows of Tingle, and does view him currently as more important(this is obviously a fact at this time, although that could change).
I do think however Tingle is a LOT less likely cause of the Villager's Up B being from Balloon Flight. Unless Tingle would somehow fit as a Villager (semi)clone, I can't see it happening yet. Especially since Tingle's biggest 'charm' indeed would be in his balloon-based moves. Or at least, being the actual spiritual replacement for the ever-left-out actual Balloon-Fighter. And I don't really see him being his own series. Much like as you said yourself, Dr.Mario was listed with Mario, Luigi, Peach and Bowser. He was probably listed as a Zelda character on the Brawl Dojo to when he got confirmed as an Assist Trophy.
To be fair, Dr. Mario also got in due to the music being wanted. But the thing is, maybe he didn't want to give him his own symbol? Who knows? The Dr. Mario series wasn't nearly as notable as the Wario and Yoshi series, being that it was (at one time for sure, now it's questionable with Miyamoto's statements) just another Mario anyway, so a different series symbol wouldn't be worth it.
Impa has the advantage of a new, strong, revival role in the series. And being similar to Sheik in a way. That should give them enough to write a moveset for her. Even though there's little demand for a Zelda character, she's still mentoined quite a lot in the Smash fanbase. The idea just gets opposed too much by people who are looking forward to see all previous characters back. And somehow, the idea to say, replace Lucario, Ike, or heck even Falco is far more widely accepted than Sheik. Is that cause the Zoroark, 'Newtwo', Chrom and Krystal fanbases are bigger in general than Impa's? Or that Zelda / Sheik's 'unique factor' warrants their stay?
She can be mentioned often in the Smash fanbase. But she hasn't been mentioned at all by Sakurai, which is the most important. I think the reason all of those are more acceptable cuts is because, well, Sheik is key to actually playing Zelda at her fullest. She's still part of Zelda in Smash. Ike is a standalone character, and many thought he replaced Roy, so him going away doesn't bother them as much. Same with Lucario and Mewtwo. Falco is more acceptable to leave out because Wolf is a villain, plain and simple. Likewise, he's still heavily a clone, while Wolf is barely similar to Fox at all(he has two similar B moves, and that's quite literally it. Maybe the throws as well), so it makes sense to remove the clone for someone unique. I'd actually prefer to keep in all of those mentioned, to note.
It has already been stated that Sakurai will most likely not be able to bring all previous characters back. So I'm not seeing why people are more open minded on who is staying and who should go. Especially since game balance is apperantly a major focus this time around. And for that to happen, I need to see a lot of changes. Luckily, with Bowser getting such a huge moveset revamp, it's not hard to see changes for characters who also suffered for their lack of competitive prowress in the last couple of games. Aside from Bowser, the biggest examples I think of are: Yoshi, Ness and Zelda. All have constistantly been low tier, or far worse. Ice Climbers also stand out, cause their chaingrabs always made them end up in the northern hemisphere of the tier lists. Sure, Samus, C.Falcon and Jigglypuff are also bad in Brawl, but at least they where very good in Melee (or at least, balanced in Smash 64). This is what separates them from the others.
I doubt he would remove Sheik since it was Nintendo that wanted Sheik and Zelda in during Brawl, not him. In Melee, we don't know the score, but Sheik had an entirely unique moveset made by Sakurai(save her Up B and Down B), while Zelda didn't have anything of her own for B moves, save Transform. Basically, when you gotta borrow more moves from Link, you can tell who he viewed as being more fun to create. But then again, it was easier to make a Ninja over a magical princess with no defined powers and one canon move.
Anyway, if Sakurai wants to add a recent character from the Zelda series, I think the biggest bets are for Impa to become playable. Then again, with this game looking so much like Brawl, it's releatively easy to bring Sheik back in the game. However, it's equally easy to remove Sheik, give Impa a few of Sheik's moves, and make her a separate character. A 'lazy man's newcomer' so to say. Can't quite make up my mind, but if he's gonna change movesets around anyway.... Ah well, can't expect anyone to simply agree with me on this, but at least I hope to broaden up some basic understanding.
He only cares about recency in Pokemon and that's it. He may care about it for character designs, but he never actually showed this for other series overall. I doubt he'll apply it to Zelda either. Also, it'd be dumb to replace Sheik instead of just making Impa her own unique character with perhaps some slight similarities to Sheik. Basically, like how Lucas was. He was partially similar to Ness, yes, but he was extremely unique as well. Or Wolf, if you will.
Also, I was heavily dissapointed Zelda was so little changed from Melee to Brawl. I had hoped she used a light sphere instead of Din's Fire, use her rapier from Twilight Princess, and her Light Arrows as a regular special. Also that Triforce light magic spell she did in Twilight Princess. Felt she really established her own abilities in Twilight Princess and Wind Waker, and didn't had to rely on Link's spells from Ocarina of Time, and Sheik. So, yeah, I wanted Sheik gone already since Pre-Brawl.
Sakurai doesn't care about balance, he cares about making them fun, apparently. I guess he doesn't care about Zelda herself more than Sheik. This isn't too surprising, since only Toon Link and Sheik aren't horrid characters in Brawl. I guess he likes the non-main 3 better? Actually, correction, he clearly does. He did do the balance himself and knew Ganondorf was trash(this isn't hard to tell, since even with Items, he sucks). Link and Zelda are harder to say, but Link was definitely worse. Actually, so were all of them. Sheik dropped down in her status of good from Melee to Brawl, but she didn't suck whatsoever. Young Link and Toon Link are around the same level. Link was made pretty trashy. Zelda, I think she got worse? I haven't checked the Tier list.
Also, keep in mind again; Nintendo wanted Sheik and Zelda both in Brawl, not Sakurai. Even if they don't give new designs for Sheik, Sakurai still likes Sheik as is and probably will keep her in regardless. Impa does have a fair chance along with Tingle as new slots. I also doubt he cares about how many slots each series gets either. Whether it's based around amount of games, or whatever. F-Zero has less slots than Mother, despite how many games each has, and so on.
@KumaOso: No it doesn't sound unfair to me. Zelda does need to be better, but I believe they're better off as a combo character as that's what made them who they are and worth playing the most. They never were meant to be played separately, regardless. Also, way to miss my point anyway. Zero Suit and Samus are viable on their own only because you can't transition between them easily. Sheik is not very viable in Brawl and was made specifically to rely on Zelda to finish the job. I find that fine as a concept 100%. I don't see any legitimate issues with this as long as they can transform a bit faster. Yes, some work needs to be done, but separating them is not the answer. Likewise, Pokemon Trainer is fine just like that, but his possibility of staying is up in the air due to the 3DS limitations.