After trying and failing to find some way to make a semi decent looking company directory with ootb parts, we've decided to just redirect people to _layouts/15/search.aspx/people, which works fine, but they appear to be sorted in no discernible order. Is there a way to change the results to be sorted alphabetically?
You can not customize the search results as we used to do in the classic search result page as mentioned here.
However, you can use the PnP Modern Search web part as described in this post SharePoint Online – Search Options Today.
You can find the details about Pnp Modern Search from the below link.