ALA is interesting for a day or 2 but you could use it a springboard to Uzbekistan which is a phenomenal place to visit. Air Astana connect ALA and TAS, fairly cheap and a very good airline.

I've heard good things about Kyrgyzstan but I think it is a very outdoors type place.

Khartoum?

Don't let my whinging put you off ADD. There is a ton of history - and the chance to earn some miles on ET domestic flights too - but do go prepared with loads of Immodium.

If you do plump for RAK hire a car and get out of town too. I've just had a couple of days in Essaouria which was delightful.