I doubt it'd be the same. He would have encountered them and not give a fuck about them. Only reason he actually cared enough to save them when he got back to Holad was because of his previous encounter with Aiko who asked him to not pursue that "lonely way of life". Quoting ch. 86 "However, he could not just bluntly answer with a “NO.” As for the reason, he connected that answer to the words Aiko said, “lonely way of life.” Meaning that if it wasn't for Aiko he would have abandoned them.
So my guess is that he would have still joined the Adventurer's Guild and go to Haltina along with Yue since that'd be one of his few choices to find a Great Dungeon, this would mean at the same time that Shia would be captured by the imperial soldiers and they'd never meet. Would Kaori want to follow Hajime?? Maybe, but by this point he would reject her same as he did with Shia in the beginning. It would all depend on how persistent Kaori is, but mind you, here Hajime doesn't have a harem and he's making his feelings for Yue clear so she might give up on him once she realizaes that he won't look at her.
From there it'd be a huge setback without a beastman/woman to guide him through the Sea of Trees.