So I've found that the more I play Palutena, the better I become with her. That sounds obliquely redundant, but what I mean to say is that it's just sort of happening naturally. I find that actively trying to improve with her is just inherently perplexing, so I go with what my gut instincts and just take battles as they come. I'm racking up some decent victories so far and I'm sure there's even more for me to figure out!
Changing from Celestial Fireworks to Lightweight was a good choice, I think. I think that giving Palutena some more speed and agility helps her rush down opponetns and get them going in the air, while also enabling her to get out of the fray if the battle becomes too intense for her. I've also taken a shining to poking tactics, letting my opponent come close before tripping them up with d-tilt and, if I have some room to manouver in, dash. It catches people off-guard and works particualrly well on close-range fighters like Captain Falcon and Little Mac. A good balance is important here: rush them down when Lightweight is active and they're trying to sot out their approach, then let them come to you for their inevitable counter-strike and let 'em have it with up-smash and, if they're lose enough, side-smash. She isn't easy to get to grips with my any means, but I'm sticking with Palutena and I have to say, I have yet to reget it.