My favorite Arabic looking font is called Samarkand, and you can find it at Acidfonts.com - note the alphabetically listing of fonts at the top of the page link to all the free fonts on that site - go to "S" and it should be in the first two or three pages. It looks very Arabic, but still readable.

GP

PS: I used that font for my February 2008 Map Challenge...