Jordan, for sure. Republic of East Palestine all the way.
The Gulf States...frankly, the Gulf States never really caught nationalism. The residents had (and largely still have) a very traditional clan-based society and low populations. By the time the population started getting educated and cosmopolitan enough to be exposed to ideas like nationalism, they were being happily smothered in a generous welfare state that gave them whatever they wanted at the low price of staying completely uninvolved in politics. Not to mention, all but Saudi Arabia were more or less British protectorates, and the British were happy to help suppress Arab nationalism, which by then was obviously not going to be good for the UK.
Saudi Arabia is doable. The Hedjaz is actually the birthplace of modern Arab Nationalism, and the larger population is also traditionally richer and more exposed to the world (especially in the Hedjaz, from the Hajj). Ibn Saud (the original) is basically untopple-able. He commands fierce loyalty from a strong core of skilled soldiers, and is strongly supported by his tribe, and already by some other of the more conservative-minded imams. But he died in 1953, and his son Saud was a different kettle of fish. Saud al-Saud had pan-Arab sympathies, but that didn't stop Nasser from funding and supporting the Free Princes movement, which was supported by some of the (tiny but growing) Saudi middle class and princes lower down the line of inheritance (Talal al-Saud, the leader of the movement, was ibn Saud's 20th son).
The Free Princes called for a constitution, pan-Arabism, the rule of law, a cabinet controlling the power of the king...all that good stuff. They were able to get some good power and influence during the Saud/Faisal conflict of the late 50s and early 60s, but they changed sides one time too many and ended up getting exiled to Cairo after Saud reconciled with Faisal after the latter's rise to power. It's possible that if they'd played their cards a little better, they would have been able to prevent the reconciliation and consolidate a role as kingmakers, following it up with most of their reforms, Talal eventually serving as a powerful Prime Minister "under" whichever of Saud or Faisal ended up on top. Outright republic is even possible, if the two of them end up weakening each other sufficiently, and maybe Nasser is willing to help the Free Princes more - but I suspect that a constitutional monarchy would be preferred, since even the Free Princes were liberal only by comparison, and an attempt at republic would just result in everyone condemning Talal for trying to make himself king "out of turn".