the arabs relied heavily on cavalry.
Another misconception. Most armies relied heavily on cavalry in the early medieval era, and the Arabs do not appear to have been significantly more cav-heavy than the average. In the initial conquest phase, there are many accounts of Arab armies fighting on foot in spear formations. Sometimes they appear to have campaigned on horseback but dismounted before battle. By the ninth century we're not really talking "Arabs" any more, but a number of successful later Muslim armies -- ie, the Almoravids/Murabitun -- were also fighting in disciplined foot formations.