Well, CDavis7M, Wario's Woods jumps out at me a bit in that it's a puzzle game that rather than control the pieces directly, you control them via running around as Toad while Birdo and Wario try to shower you in new pieces, which always made it feel like this puzzle game with a slight platforming emphasis.
Sonic Mania has a part where the game momentarily stops for a bout of Puyo Puyo because Dr. Robotnik's Mean Bean Machine was a thing that happened.
I'd probably say something in the vein of the Puzzle Fighter stuff would be what you're looking for, but that's more a VS. Puzzle game with some fighting game flavoring more than any actual fighting game type mechanics.
sadly, I think your best bet is probably looking into the indie space or the mobile space. Puzzle Quest came before Puzzle & Dragon, which... yeah. not a lot of 'innovation between those, heh.
As for me, I think I might be done with Henry Hatsworth and the Puzzling Adventure. I do not find it fun, simple as that. The platforming is rudimentary and plodding, there's a godawful focus on combat where enemies take way too much damage and are placed to be as frustrating as possible to remove. maybe this would be more acceptable with better checkpointing or if the game had a better sense of flow to it, but it has neither of those. If I were making this game, I probably would have removed the cash shop stuff and put the onus of damage upgrades entirely on building up combos and chains in the puzzle, and not just to fill a dumb meter.