AFAIK Muslim tech does not get the CB from expansion ideas, so you'd want to westernize to use that, feeding previously vassaled nations or hordes. You could get a western border easily enough after beating the Mamluks down though, with a simple sniping of a province in Morocco that's low tax + borders Portugal (or if they retook the Portuguese core there, just take it directly). Muslim tech is one of those that doesn't need exploration to westernize because you can see western nations outright. Heck, you could even vassal a minor in Europe and sell them something of Mamluks to get your western border potentially, depends on alliances.
One reason I don't like expansion early on Hejaz though is that it pressures their ADM groups too much. You definitely want something to reform government, because while tribals don't suck as much as before they still don't get any -LA. Then you're going to add expansion on top of probably administrative ideas while still wanting things like military, influence, diplomatic, etc and having problems actually reaching them since you need the expansion finisher for the CB and you need the ADM (or Economic or Innovative) finisher to reform. On top of that, you might want help dealing with Shia and Ibadi provinces, with +1% strength in your NI being both late and weak. I'd prefer religious over humanist here; +2 NI and Sunni leaves you at +3 TTF and you're not far from a 3rd missionary if you go that route so you should be able to tear through everything you need to convert. I suppose it's possible to force convert nations like Oman first, then vassal them, allowing vassals to convert your future land at the expense of slowing you down a bit in terms of conquest (Persia takes religious too, so as long as you can convert 1 low tax province, you can release them Sunni and then make all the things Sunni).
If it really bothers you, it's worth noting that you could in theory go exploration, explore what you'll care to colonize, then dump it, but that costs 700 DIP so it's not a trivial investment. Exploration colonies are faster due to the settler growth rate and extra colonist too so if you're big on colonization it's faster. As Hejaz the colonial priority is Cape IMO, not to the East, because the East is all tropical other than Maldives and islands that are considered African (IE distant overseas) until northern Taiwan. Cape you can make same continent in addition to controlling the powerful Zanzibar node and is temperate. Normally I don't advocate going there as an Asian nation because it's distant overseas and there are faster ways to westernize but for Hejaz I can't think of a better early colony target.
IMO Aristocratic is a super obvious early military pick for Hejaz; they already get -cavalry cost and their ambition adds 15% combat ability, and they keep their 80% ratio forever. Eventually you'll phase it out a bit, but you'll be able to knock heads pretty easily with it early on.
