The thread seems rather dead, but I thought I'd pitch in my own thoughts.
"Skeletons on the Zahara" by Dean King -- haven't read it yet, but apparently an excellent account of an actual event where the crew of a Connecticut merchant ship was shipwrecked off the coast of Morocco and enslaved by Arab traders.
"Sharpe's Tiger" by Bernard Cornwell -- technically this story is set in India, but as there was a great deal of cultural exchange and mingling between India, Persia, Arabia, the Levant, Egypt, and North Africa over the years, particularly during the Islamic period, much of the flavor in this novel can be appropriated for LoF, I think. The next two books in the series, "Sharpe's Triumph" and "Sharpe's Fortress" would also be good. The other books hold no interest as far as LoF is concerned, as they are set in Europe.
"The Arabian Nights" and "Sindbad the Sailor and Other Stories," translated by Husain Haddawy -- Haddawy's translation is probably the best in print, and there's a lot to be said for going straight to the source of things.
"Prince of Persia: Sands of Time" -- playing this game is what got me interested in the Arabian Nights and Legacy of Fire. The story is excellent, and the background music lovely.
"The Shahnameh," translated by Dick Davis -- If you're a student of Central Asian myth and history anyway, or can afford to lay down several hundred dollars in the pursuit of a better setting, this collection is an excellent addition. It is a translation of a Persian epic detailing the lives of Persian kings and princes from the dawn of time to when the Caliphs destroyed the Persian monarchy. This book is Persia in the same way that the the Volsunga Saga is ancient Scandinavia, and along with the Arabian Nights there is probably no better representation of the culture of that time and place. Be forewarned: I understand that this collection is exceptionally long.
