Speaking from experience, so long as you don’t walk around aimlessly grinding happiness for a while (which while far from optimal I have done, just zone out watching a movie or show and walk back and forth, harder without the bike though), you should get a Lucario at the earliest before Burgh. I have not personally gotten one from my playthroughs before Roxie.
Even then, I find Lucario does have some hiccups due to being forced to rely on Force Palm for fighting stab for a while. While it could always be worse, it is a noticeable gap that shows before you get better fighting stab to use. Even by the reversal mountain Lucario is left wanting for a better fighting stab from my experience.