There is Fedra and Fedra Arabic ; Palatino Nova and Palatino Arabic ; in progress, there is Cassius / Ali by Mathieu Réguer (http://www.typefacedesign.org/resources/A5specimen/2008/MathieuReguer_Ca...)...

Koufiya. There is information about other Arabic fonts on the page.
http://www.linotype.com/341155/koufiya-family.html

Don't forget FF Amman, from FSI, or another Linotype typeface… Frutiger Arabic.

Doesn't Adobe Arabic sort of gell with Minion's color, too?

Check this out:

The Typographic Matchmaking 01 project
10 Arab and Dutch designers collaborate on designing Arabic companions for Dutch fonts

Gerard Unger & Nadine Chahine
Fred Smeijers & Lara Assouad Khoury
Martin Majoor & Pascal Zoghbi
Lucas de Groot & Mouneer Al-Shaarani
Peter Bilak & Tarek Atrissi

http://www.khtt.net/page/106/en