Personally I'm also terrible at the matchup. I played 2 sets last weekend and while I felt like I was outplaying my opponents I lost stocks to gimmicks or weird situations. Also, is stomp on shield safe if I pull back enough? I got grabbed trying it.
It seems like the reason you lost was because of minor technical mistakes. From what I've seen, any grab or significant hit from Peach can net her a good 50% or more easily. Plus, once you're offstage, you're pretty much dead, and 50% will probably put you offstage. You made minor mistakes against Kuja, but they cost you a stock almost every time. It looks like you just have to slow yourself down a bit and you'll destroy Peaches, cause your combos are beautiful and you were basically running circles around him the whole time.
EDIT: Also, I have no idea what to do about it, but just don't hit peach with any aerial or gentleman that isn't overshot or retreating (Lol retreating gentlemen?) under whatever percent it is she can crouch cancel. She will dsmash you and you will die. You do it a few times, and he nails you with the meatgrinder every time.
Also, don't autocancel your early uairs at lower percents. You do it against Kuja and he nairs you out of every one, usually when you're past him, sending you offstage.
Also I feel weird giving advice to people better than me. So tell me if I say stupid stuff.