Luigi is overshadowed by his semi-clone Mario in nearly every way.
I just find his character is bland emphasizing the lanky awkward and feeble mario bro, that has overlapping abilities to mario, but somehow doesn't really offer much to the duo other than a bit of comedy, in a series that has many more comical characters than Luigi. I will say Luigi's Mansion is an exception. Mario could never pull it off quite as well; however, does that make him a good sidekick?
The year of Luigi was stagnating for nintendo. Probably one of the worst years the Mario Series has presented since its inception. Sure, New Moon was fun, but that year didn't seem to have any fresh ideas or innovative and compelling games with high replay value (Don't get me started on the never ending tutorial that is highly overrated referred to as Dream Team). So both Nintendo suffered never before seen sales losses and fans were let down (the two go hand in hand). A sidekick should know his place, especially one that doesn't offer anything on his own standing that his partner already possess in greater volume.
Midna on the other hand offers something new to the Zelda Series. Sure, I think every Zelda game had unique partners, characters, and storylines. Twilight princess at the very least has the best sidekick of the series that ties well into the somber storyline.
She is not a clone of Link, neither link possesses any personality or skill traits of Midna, or vice versa. Though, they both share a common goal, well at least they eventually share this goal, as Midna reveals her own selfish motivations -- restoring her world and her own beauty/identity. But, think, she has never learned to show compassion or selflessness in her environment, Link (and Zelda) were able to show her this compassion, which gradually led to her change of heart, and humanization. In return, she was able to impart Link with the strength of staring fear in the face, while smirking. Reciprocal character development is a toughie to pull off, usually characters develop separately or all-together undergo the same revelations.
As far as personality goes, Midna is one of the most memorable characters and Zelda creators definitely pulled off her sarcastic, glib, charming, and playful demeanor perfectly. Those characteristics balance out Link's calm, stoic, and straight-forward attitude.
The plot actually shows the development of the characters' relationship as partners in a graduated fashion, that doesn't feel forced or unrealistic (as many games, even good ones, seem to force revelation after the other which seem a bit unauthentic to say the least)
This genuine struggle and actual development of a dynamic relationship trumps the static and unmoving/lighthearted bond between Mario and Luigi that rarely scratches beyond a surface-level relationship.
With that said, I can confidently cast my vote for Midna!