Kirby vs. Dedede
This match-up is very close to even, but if anyone has the advantage I would wager it would be Kirby.
Dedede
Advantages: Good Reach, Heavy Weight.
Disadvantages: Slow Air Speed, Slow Ground Speed, Slow Attacks, Large Size
Kirby
Advantages: Small Size, Strong Attacks, Combos, Attack Speed, Recovery
Disadvantages: Light Weight, Short Attacks
General Observations
Kirby can get damage in bursts, especially when striking at low percents. Dedede isn't especially difficult to get off-stage at which point Dedede's campy offense is negated. However, it's that same campy offense that can keep Kirby at a distance, building damage, and putting Kirby at a growing disadvantage.
Contrary to one's initial thought, it's really Kirby who has the better KO options in this fight. While Dedede houses some extremely powerful attacks, they're much less likely to land or sweet-spot on Kirby. Dedede will often times have to rely on weaker attacks due to speed or reach, especially when the Kirby player is smart enough to avoid the dreaded U-tilt. Kirby on the other hand has several attacks that hold enough power to net KOs that also have enough speed to punish a mistep from Dedede.
At a distance, Dedede's Waddle Dee Toss can prove useful, but Kirby's Final Cutter can be used to skillfully knock them away as well as send a Cutter shockwave through any number of Dees, Doos, and Dededes. Both characters have considerable lag to punish during these projectiles, but due to the slow speed of these fighters optimal punishment can be difficult.
The real battle takes place where projectiles can easily be shielded or Dodge and close enough to punish. At this distance, Kirby is looking for a way to bridge the gap and get some solid damage in while Dedede is keeping an extra step away to get the first hit with his long reaching attacks. Once Kirby and Dedede get into close quarters, Kirby is either approaching with an aerial, a tilt, or going for a grab - Dedede's options at this time is a 'stop-thrust' (holding out an attack for Kirby to run into such as D-tilt, B-air, etc.), Shield Camping (usually to net a grab), or to pull back and re-establish distance.
A decisive part of the fight is in the off-stage battle. King Dedede is less mobile and predictable upon his recovery than Kirby because Dedede's Jumps are shorter, fewer in number, and sort of pathetic. Kirby is floatier, has his Hammer for horizontal mobility, and can latch onto the ledge much easier with Final Cutter than Dedede's Super Jump. However, Dedede has some very effective edge guarding against Kirby because Dedede's B-air is stronger, larger, and a lot more intimidating to the light-weight Kirby than vice versa. They both have the option to go for a Swallowcide (of which Dedede's always seems more effective) but this usually results in both players losing a stock so it requires much more stategic implementation than simply hitting the guy as an edge guard.