Most of what's written here is fact, not opinion. Feel free to ask older Yoshis (Bringer, Moo, D1, Svampen, Bigz, etc.) for confirmation.
I feel like I'm beating a dead horse by putting this first, but I feel like I have to because it's important and brings a good deal of context (something that's sadly missing from modern conversation) to what I'm typing. Smash players love their terminology (I've seen five new technique acronyms already and the game's been out for barely a week, WTF?), but it's important to understand their meaning. Yoshi's double jump is still, to my knowledge, a weight modifier. The jump increases his weight by some factor (in Melee it was a 300% increase) and the increased weight gives him what is equivalent to (and I do mean equivalent to) an aerial crouch cancel (in Melee terms, at least). Since the notion of crouch canceling disappeared with Brawl, I'm not entirely sure how the weight calculation changed (probably got a bit more complex), but the important take-away here is that the jump isn't an armored jump--beyond the terminology, this knowledge gives some insight into why the jump works the way it does any why certain things beat it early or can't beat it ever.
Another thing that I want to point out is that, when talking about one character being a better character than another, it's important to add context to that idea as well. Are you saying CharacterX consistently beats CharacterY or that CharacterX is better than CharacterY at the game in which they're played? Two very different ideas that, more often than not, yield very different results. Making the distinction matters.
On to some history.
Smash 64 was a crazy game because everyone was absolutely ********. The stupid part is that the best characters were just that much more ******** than everyone else to make them stand out while still making the game fun for most other characters. People like to dump on Link and Samus in this game, who were the two worst without question, although Link was still threatening on stage while Samus was not very threatening in many places at all. Yoshi was in here and did stuff, mostly damage (64% down air #Kreygasm), some shield breaking (up tilt yessssssssssssss) and cool, but akwardly slow DJC stuff. He was huge and heavy and didn't have much range outside of his smashes and forward tilt. Standard throw game, but having DJC and Egg Lay made characters very scared to shield (shielding was almost a no-no in 64 for a good deal of matchups/certain normals) and DJC normals like up air made characters mostly afraid to poke out in retaliation, so characters had to rely on good movement and the stage to get around Yoshi's fantastic damage and actual shield pressure. This is the beginning of the unfurling of one of Yoshi's primary weaknesses--chasing down mobile characters. Egg Toss in this game was very damaging, but difficult to control and wasn't very flexible while his jump and double jump were not quick either.
Melee was interesting because the game was super technical straight out of the gate in 01, with stuff still being found and named years and years later. Yoshi was even more interesting because of the extremely deliberate design choices made for the character. Melee Yoshi is infamous for not being able to actually play the game; by that, I mean there were several universal system mechanics that Yoshi either could not employ or had to use watered-down variations of in order to be effective. Melee started the shield jumping restriction, but gave him powerful lightshield and supershield (or parry, as its more widely known) mechanics. Eggs became more critical to gameplay, by making them more flexible, travel faster and knock back less, but cover more angles. Yoshi became a bit smaller in his frame while gaining some range through stretching and bending for attacks (moreso than in 64). The game was very combo oriented, so Yoshi's moves became less about KO power and more about leading into the finishing blow after a long combo. Yoshi still had damage, but took some damage hits on some moves, most notably down air (reduced to 54%). In keeping with the combo game mentality, Yoshi's throws also became more about combo starters than about knockback.
Yoshi's moveset in this game was actually quite scary; he had combo moves, KO moves, moves that had static knockback, moves with lots of disjoint and moves with partial invulnerability...the toolkit was borderline busted, but it was just not assembled as tightly as it could have been. A prime example of this is Yoshi's grab. As these games operate in discrete time measurements known as frames, motion over time is also considered to be discrete (or step-by-step) instead of one smooth motion. When Yoshi sticks his tongue out for his grab or dash grab, the grab hitbox lies only on the tip of his tongue. What this means is that as the motion for the grab occurs over time, there are gaps in the area that the grab hitbox will cover. Small enough or thin enough characters that are in the right place at the right time can have Yoshi's grab "pass through" them completely. What's happening is that the opponent's vulnerable areas are nested in the gaps between the portions of space covered by the grab hitbox on Yoshi's tongue. This phenomenon became even worse with the dash grab because the grab covered the same space over a smaller amount of time (Yoshi's tongue came out much faster for the dash grab, meaning the gaps between grabbable areas became much bigger). The grab hitbox for the dash grab also expired before Yoshi's tongue reached its visual limit. All these factors combined to give Yoshi one of the worst grab games and the worst dash grab game in Melee. In a game like Melee where you are only as strong as your most exploitable weakness, this was fatal for Yoshi as the game, over time, began to revolve more and more around grabs and how powerful grabbing was, even if the throws themselves weren't consistently good for all the good characters.
Defensively, Yoshi thrived by living on the edge in both senses of the term. He had a great ledge game with eggs including the oppressively technically demanding, but equally incomprehensibly effective reverse-edge-canceled-egg-regrab-smashname-somethingorother. He also got great mileage out of the nuances of his shield mechanic, with recent Yoshi play involving wowing spectators with defensive maneuvers that take place in windows no larger than 2 frames. Lightshielding with Yoshi was an extremely potent way to make space quickly in hairy situations and Yoshi even had a way to force powershields without pressing additional buttons. Yoshi's dodges were average (although the part of his air dodge that determined the height from which he could grab the stage was unfortunately not very high up on his frame), but his roll was unique because of its displaced vulnerability frames. Instead of being vulnerable where everyone else's rolls were, Yoshi's vulnerability frames were moved around and adjusted for a few reasons which are educated guesses on my part, but still unconfirmed.
Yoshi's matchups in Melee were extremely unfortunate. In a vacuum, Yoshi is actually a decent character in Melee considering the engine and his traits, but he suffered from one of the worst matchup spreads in the franchise's history. He had losing matchups in both extremes of the character quality spectrum and had two of his worst matchups ever right in the middle (Mario and Samus).Yoshi's Melee tournament viability has always come from tirelessly exploiting his strengths in his tilt game, movement, mastery of his shields and mastery of the DJC. While he still suffered from runaway game plans, he could turn mistakes into stocks taken. Sheik was public enemy #1 for years, but techniques for escaping chaingrabs emerged (chaingrab, dash chaingrab and pivot chaingrab work only up to 56%, at which point getting out becomes possible, but extremely tight the closer to 56% you are) and Yoshi players upped their mobility, making the matchup still horrendous, but technically playable. Fox and Falco were volatile matchups for Yoshi just because all three characters were so good at doing damage, but the matchups were generally a wash just because of how much better Fox and Falco were at the game overall. Marth, Ice Climbers and Peach were probably Yoshi's easiest tournament matchups, although that isn't saying much as these matchups were still hard, but they were "regular game" hard instead of "NASA level mathematics" hard, with Ice Climbers being probably the easiest "good character" matchup Yoshi had in the game. Out of the characters of lesser quality, Yoshi's harder matchups were with characters like Mewtwo, Ness and Zelda (all DJC characters, interestingly enough). The ugliest matchups Yoshi has ever had in any Smash game by far, however, are right smack in the middle with Mario and Samus. Generally classified as "really bad" by most players that have intimate knowledge of these two matchups, I personally consider them unwinnable by any stretch of the imagination. "Fighting Samus with Yoshi is like fighting a tank with sporks from Taco Bell." The Mario matchup wasn't very much different. The match with Samus involved her being able to CC Yoshi's entire offensive array while outdamaging him in every possible situation with bigger, better hitboxes and a wider array of tools that were effective in more ranges and at more angles. The match with Mario was less about Mario's traits and more about the fact that Mario abused all of Yoshi's weaknesses more succinctly than any other character in the game, hands down.
Brawl brought along a whole slew of silly, silly things (what a silly game). Yoshi became smaller and lost some his range, but most notably lost damage (especially on down air again, down to 33%) and KO power (up smash and downsmash, especially). Yoshi lost the manual DJC, but retained a lesser version using Egg Lay to force it. He lost manual control of his eggs; they instead had preset rails they would ride on depending on the initial angle of the throw. Yoshi's dash grab became a bit better, although it still would miss opponents occasionally and he gained a very potent pivot grab. He lost all of his shield tricks but still did not regain the ability to jump out of shield. All these changes meant Yoshi had to morph into a defensive character simply because he could not shoulder the risk of a predictable and risky (the worst combination) offense. He had to use mobility, augmented largely by DR (a powerful technique which let Yoshi control his ground spacing despite Brawl's slippery movement engine) and a very solid ground game with tilts and jabs and defensive pivot tools to hold his own. Again, this would be Yoshi's undoing as Brawl became a game of aerial combat and option reduction. Yoshi's tools would match up only as far as he could force it; he simply did not have every answer for multiple situations and became a very heavy commitment character, albeit without the heavy risk (and the bountiful reward) that came with Melee. Relatively, Yoshi improved over his Melee counterpart in relation to the other characters in the game, even though in a vacuum he became worse. The character was actually seen in tournament and had several names represent him well, which is much more than can be said for Melee Yoshi.
I was going to devote this paragraph to Brawl matchups, but I realized they didn't matter in the grand scheme of things.
All of this brings us to current day Yoshi. I'm excited for his changes (I'll save the nitty gritty for another post), but the thing that concerns me most about him is his current inability to really control what's going on in a match. I think when the WiiU version drops and controlling the character will be much easier universally, this may change and of course as people get more comfortable with the character over time, this will change. Yoshi seems to not be able to really force situations and reduce options in these huge stages and he is currently lacking in the movement department outside of some pivots, so I think the push early on for Yoshi should be twofold: first, to really rebuild his ground game from scratch and learn how to exploit it (this was the most important thing for Brawl Yoshi players to learn and it took them the longest, in my view), especially since so many of his critical KO moves are aerial and you want to keep those ready; second, to really invest time in solid ways to increase Yoshi's movement speed and options, not anything gimmicky or unreliable, but real ways to get places faster and to allow Yoshi to attack from more angles. I think that even though he doesn't get to control a whole screen, one of his strengths I'm noticing so far is that he can put the opponent in some situations where they are forced to act first or risk taking an obvious power hit and from here he can then react to what the opponent does, but I don't think this happens often enough and during enough common situations for this to be a reliable strength. If Yoshi is going to break into that upper echelon, I think it will be when his players become smarter, more precise and more mentally agile than they have been in the past.