Took a few weeks, but I finally understand the source of most of my performance issues. Allow me to illustrate the problem with one specific example. Here's a bit of code from my "CheckAttackInputs()" function:

If the player pressed B, we can continue checking if they were airborne (to perform a jump kick!).  The "IsAirborne()" function looks like this:

Inside, we call "GetHistoryFrame()", which looks like this:

And that calls "history:GetFrame()", which looks like this:

Hopefully, you're beginning to see the problem.

I had tons of helper functions like this, all which called "GetHistoryFrame()" in some way. Turns out this Function:Daisy:Chaining() is actually pretty slow in Lua. This sucks for me, who likes having lots of little helper functions to keep the code tidier and more readable. All those "GetHistoryFrame()" calls were adding 10-20ms on average during an update, which slowed things down significantly.

I've since removed a lot of those helper functions, and am now accessing the history directly. This resulted in me doing a lot of ad-hoc checks:

This isn't the worst thing in the world, but I really liked keeping logic centralized in those little helper functions. Now, if I ever need to re-factor airborne checking, I'm gonna have to do it in multiple places. :\

Still lots of bugs to fix, but the worst one is under control now. Give it a shot, and let me know it plays for you!