Not exactly fantasy literature, and purporting to be fact (though more likely heavily embroidered fact), for Levantine sagas I recommend:
Usamah ibn Munqidh, An Arab-Syrian Gentleman and Warrior in the Period of the Crusades, trans. P.K. Hitti (ISBN: 0231121253).
The "memoirs" of a Muslim emir who travelled widely, knew Saladin and died in 1188. It's worth it just for the chapter on crusader habits...
My turn!
Since we're in a levantine mood, may I recommend:
The Arabian Nightmare, Robert Irwin. Will give the devious storyguide all sorts of sneaky ideas.
Gerfalcon, Leslie Barringer. More of a low-key, low-fantasy book set in the approximate Ars period in a rural faux-France.
Another little gem I just remembered on my shelf (since as you say, Wolf, we are in a Levantine mood) is a very readable collection of fictional stories on the Templars derived in some small part from historically factual snippets as much as from legend.
The book is entitled Tales of the Knights Templar, edited by Katherine Kurtz. Stories are sourced from authors such as Poul Anderson, Deborah Turner Harrison, Elizabeth Moon and Katherine Kurtz herself.
Worth a read for story seeds or some roleplay concepts for Knight Templaresque companions or NPCs I suppose.
Ohyes... I stole characters left and right from that book to toss at my players.
Wonderful book really.