Kufi Standard GK is probably the best choice of the mentioned typefaces. The geometric appearance of the typeface slightly matches the appearance of Avenir.

I was looking at that, but I wasn't sure if it was really forced. That is to say, I've heard people talk about trying to make Arabic type (or any other language system) "helvetica-ized", and completely losing the forms in the process. It looked to me like it would be the equivalent of a "techno" font, with really forced curves and lack of contrasts. I think that first, I want to make sure that the letters look good, then matching avenir comes next...

It is true that Kufi doesn't look like a traditional Arabic typeface due to its geometric nature. However Dubai doesn't have the appearance of a typical middle eastern country. I have recently seen a lot of Arabic geometric typefaces in use, most memorable was during the recent Bahrain f1 gran prix and this years TDC winning text family Al Rajhi. I personally really like them. I can understand why many Arab nations believe they are an insult to their cultural traditions.

I am guessing Arabic geometric inspired typefaces haven't been around for a long period of time. It is only a matter of time before they become more accepted in certain countries like Dubia and Bahrain. The west had similiar acceptance issues with grotesques and early geometrics during the early twentieth century because of the radical change.

I would give it a test setting to see if it works. If it does still feel to "techno". I would use Nadeem or Geeza since they appear slightly minimal but still have an element of Arabic calligraphy to them,

You might try UKIJ fonts, a wide variety there. Also, SIL puts out Lateef and Scheherazade, both nice looking. Finally, there are the Paktype fonts. Any of these may suit you. Check the license first.
Personally, I'd go for a nice Nastaliq, or Sulus face for any names.

Why aren't you using whatever service others use in-country? There likely is some "standard" font, layout, etc., and it might be better to fit in rather than splash in.

The DecoType Naskh we made is the Arabic equivalent of, say, the Times New Roman so it's always a safe choice, though in our eyes technically obsolete and too simplistic. We also licensed a Thuluth to Apple based on the same simplified Apple template, so you should be able to use that a s well.

If you want access to our new high-end typefaces for this one-off job, you can contact me directly as tmilo [at] my company dot below.

Thomas Milo
DecoType
www.decotype.com

The DecoType Naskh we made is the Arabic equivalent of, say, the Times New Roman so it's always a safe choice, though in our eyes technically obsolete and too simplistic. We also licensed a Thuluth to Apple based on the same simplified Apple template, so you should be able to use that a s well.

If you want access to our new high-end typefaces for this one-off job, you can contact me directly as tmilo [at] my company dot below.

Thomas Milo
DecoType
www.decotype.com