Alright, I'm open if anyone has a better idea but my solution so far is this:
1. Store a variable that holds the maxSpeed the AI can run.
2. If the current animation is idle and we want to change to a movement animation, immediately change
3. Otherwise, if we're in a movement animation, stay in this animation unless our velocity exceeds maxSpeed * .8f in the direction we want to change.
If you wait until the velocity hits maxSpeed the animation change looks delayed, but if you set that range too low it doesn't catch all of the sudden changes. .8f works fine in my case.
I haven't had any problems so far... fingers crossed this did the trick!