If I'm picturing what you want correctly, here's what I would recommend. The source for the underground bit is from when I was an urban planner in the middle east.
Distance
Your settlements should be no further than a two or three days trek by camel/caravan. While you can go further, some of your perishables (dates, fish from the sea, camels milk) should be kept in a cool place, and by day, the further from the sea or your two mega-cities will get very hot even in the winter. You ideally want respite and water for camels as well after a couple days. Wayfinding for settlements much further apart gets difficult, if you're off by even 1°.
Depth
Water and sandstone can be found in just 3m depth in the Rub Al Khali. Sandstone is marvelously pliable (see this question). There are also many instances of troglodytes in desert areas, particularly the many in southern Tunisia and North Africa. For instance, Matmata has just a few entrances, but holds a whole warren of tunnels and dwelling units.
Size
Your size of underground caves is up to you. However, keep in mind that you need access for materials in and out, including waste. The old oasis of Tozeur was about 700m x 700m, but you want yours to be underground of course. This is because the 5min walking distance from the central mosque is considered about 350m radius in planning terms. Presumably your central entry/exit could be the same - give your underground dwellers a 5min walking distance from the entry/exit.