Blade, as someone with a pretty good idea of what you like in video games going back ten years now, I am shocked you haven't played KH. When it came out, the first one was the closest thing to the kind of fighting game experience (Advent Children in game form) that you've always wanted.
Keep in mind that the KH team is also responsible for Advent Children and FFXV. Appreciating that last one will only be improved by getting familiar with KH. I really think you would enjoy the hell out of at least the original, II, Birth by Sleep and III (whenever it comes out).
I think you should get the KH HD I.5 ReMIX collection and at least play the first KH. Re:Chain of Memories is still CoM, so the gameplay suffers in comparison, but the story is good and sets up KHII well, and, thankfully, the edition of 358/2 Days included in the set is just a two hour, fifty minute-movie.
KHII brings more of the awesome gameplay the original offered, but it's even better. I'd say just wait for the KH HD II.5 ReMIX collection to play that one, though. Unless you're just that hooked aftee the original, which is entirely possible.
Birth by Sleep also has good gameplay. One of the PSP's better games, and definitely superior to Crisis Core.