So I had the honour playing some Dededes today and I think this matchup is not quite as difficult as I thought it to be. It's still a tough one, don't get me wrong, but it's much more bearable if you're savvy and play cautiously.
I've noticed that, due to his massive hitbox and weight, Dedede is combo bait. D-throw -> sliding u-smash works especially well against him, since even if he DI's out of it, he's big and heavy and will have difficulty getting too far without a follow-up f-air or u-air on his tail.
I've seen a lot of (probably not very careful) Dededes using dash, which is very powerful, but ridiculously easy to shield-grab or dodge behind. Basically a free grab / smash if you shield it with proper timing.
Be conscious of his range. He only has one long-range move, but he's huge and his hammer has great reach. DO NOT ATTEMPT TO INTERCEPT HIS SMASHES. I keep foolishly trying to swoop in and strike with a dash or d-air while he's charging, and it never, ever works. He will kill you. You've got to respect his space and keep him at a safe distance. Arrows and f-tilt will ensure he never gets too close, because if he gets in your space and you're unable to shimmy out of his hitzone, you're going to die. End of.
DO NOT CHALLENGE DEDEDE IN THE AIR. He has better range, stronger KO options, faster moves and a much, much bigger sphere of influence. Just don't do it. Keep him at bay with n-air, f-air and u-air if you so choose, but do not try to have an aerial battle with him. He will smack you down hard and it will not be pretty for you. Landing is another story, and especially if he cancels his up-b and enters freefall, you have plenty of opportunities to hit him. Sliding u-smash or n-air / u-air are both good in my opinion, and the more you can juggle him, the more at a disadvantage he is put, and that is exactly where you want him to be.
Keep him at a distance. That is the best strategy I've found for fighting the king. He may try to toss out Gordos at you, and this is good: it means you can get a free hit by rebounding them! If you're keeping up the pressure with arrows or throwing out empty n-airs, chances are you'll be in the right position to hit them back - even if they miss Dedede, getting them out of your face and on the vector back towards him is a much better position to be in.
In short, I'd rate this matchup 60:40 in Dedede's favour. He's huge and he hits hard, and he trumps us in terms of range, KO power, airgame and edge-guarding, which makes killing him even more difficult than it would ordinarily be. He is incredibly difficult to kill as standard and he's near impossible to gimp effectively, so we need to really work hard and build up damage before finally KOing him in creative and inspired ways. It's not nearly as difficult as I first thought it to be (I would have put it in at least 70:30 initially before I actually did some proper research into it), and with careful resource management and respect to our skillset and his, it can be overcome.