Mario: combo game is real
Palutena: Lag + Huge hitbox = sucky character. I agree she should be higher than donkey kong, but she's clearly lower tier.
1) Mario's combo game is not real at all, you can DI out of most combos except for d-throw to up-b. Up-tilt x2 is guaranteed on big characters
2) Palutena doesn't have a huge hurtbox (which is what I assume you mean by hitbox). It's standard. It's not small, like Kirby/Pikachu/etc., but it certainly isn't big. Big would be....Rosalina and Ganondorf, maybe Ike (he's pretty tall if I remember correctly). Biggest would be DK, Dedede, Donkey Kong, and Bowser.
3) What lag? You mean on her tilts? You don't need f-tilt at all. Just use jab: it's disjointed, starts on frame 8, and has good range. It can also be followed up by grab or f-smash (jab 1 knocks the opponent toward you). F-tilt isn't a completely dead move regardless, though; pivot f-tilt covers just about everything your opponent could do and you can't be punished for it. The others... D-tilt isn't very laggy at all for what it does (way better than f-tilt and up-tilt), and you should only be using your up-tilt to catch landings anyway.
Her normals are only bad if you use them incorrectly. If you stick to SH (autocanceled) f-airs, bairs, dash attacks, Autoreticle, jabs, grabs, and the occasional d-tilt, you have a solid ground game. Consider that standard Palutena has access to Reflect Barrier as well: with that, what characters are actually beating her in neutral? Most characters' jabs and many f-tilts lose to or clash with her jab, she has twice the grab range of most characters (it's like Zelda range), her walk/dash speed is like 10th best in the game (which is very good), her dash attack is invincible, so it beats out almost every option an opponent could throw out (including projectiles and antiairs), and b-air is also invincible so SH b-airs just shut down many aerial approaches (like Ness' f-air, which would otherwise outrange Palutena).
Sword characters like Shulk and Ike have a decent shot at beating her in neutral, but her dash attack can power through their SH/FH aerials and jabs, and her jab beats theirs in close range (for some reason they use their fists for their jab 1s). Pit and Marth are probably good candidates too. Outside of them, the toughest are probably Sheik, Rosalina, and Little Mac. I'm not fully sold on Sheik, though. Palutena can usually grab Sheik before Sheik grabs her, and her jab is good against Sheik's f-tilt and d-tilt. She can also Reflect needles with little worry. It's only Sheik's f-air which is kind of annoying.
Rosalina is an interesting case. If this is with customs off then Luma Shot almost always gets Reflect Barrier'd. If Rosalina tries to n-air you can up-smash her/Luma usually. B-air consumes Luma in its vortex of invincibility. Dash attack isn't bad either for that though you'll probably get hit if Rosalina is close. The patch nerfed the Luma hitting you out of a throw animation thing so you can actually go for d-throw now, so grab is a great option in neutral.
Up to 3-5 characters beat Palutena in neutral. I think everyone else loses or ties. Duck Hunt, Megaman, Link, Samus, and projectile characters super lose, and she beats characters like Ness, Greninja, Jigglypuff (use up-smash liberally, it's a great anti-air, and your b-air always wins period), Pikachu, and Diddy (Reflect Barrier is legitimately sick against Diddy; if he side-bs the pushback is just enough for him to narrowly miss you and be open, and banana gets reflected, so there go all of his options, and if he dashes toward you you can just grab him first with your superior grab range, or just jab since attacks beat grabs now, though for all of this you need to have good spacing).
Palutena is probably upper mid or lower high tier with standard sets. She doesn't dominate anyone but projectile characters, but she doesn't struggle in any matchups either, winning neutral against many.
That tier list is non-customs, or else she would probably be top 5 on it, because customs-on makes her ridiculous.
edit: Ganondorf's neutral game is pretty good, surprisingly. You wouldn't think that it'd be any good, but it is. He's basically like a sword character. I have had legitimate difficulty facing off with Ganon in neutral. However, his disadvantaged state is still pretty bad. He's big, and he's slow, and his anti-combo options are all big commits (d-air, Wizard's Kick). If he had a n-air interrupt I'd call Ganon for Top Tier, personally.