The Gladiator soundtrack was done by Hans Zimmer and Lisa Gerrard with much of the 'middle eastern' feel of the music arguably coming from Lisa's singing. I would recommend exploring her work in Dead Can Dance, and with Pieter Bourke (Duality). In a similar vein, you also may want to seek out work by Loreena McKennitt, Niyaz, or Vas.
