I'm an American and I've been learning spoken Arabic for a couple of years and I really think it depends on your reasons for learning. I reccomend learning a dialect first if you just want to travel and converse to people.!
I only reccommend learning Fus7a first if you are a student of politics or religion.
Modern Standard Arabic is NOT the lingua franca of the Arab world
Perhaps in the realm of politics but certainly not for ordinary people.
This is one of the biggest misconceptions out there.
A lot of language products and courses market Modern Standard Arabic as the lingua franca (bridge or vehicular language) of the Middle East and North Africa. They teach MSA as a 'conversational' language that will make communication between all Arabic-speaking people possible.
It's not accurate at all.
First of all, MSA is not a conversational language. There's not a single human being on the face of this planet who speaks it as a native language or uses it in day-to-day affairs.