Israel is the only one that comes to mind. Any ostensibly Muslim nation will/does have both cultural and legal issues with women in immodest dress. Not actually in the middle east but an exemplar of the cultural mindset :
Sheikh Taj Aldin al-Hilali, the Mufti of Australia, recently (2006) preached: “If you take uncovered meat and place it outside . . . and the cats come to eat it . . . whose fault is it, the cats’ or the uncovered meat’s? The uncovered meat is the problem. If she was in her room, in her home, in her hijab, no problem would have occurred.”
Any culture that basically codifies the law to make “It’s her fault, she was dressed like she wanted to be raped” into an affirmative defense is, IMHO, profoundly fucked up and not somewhere I’d choose to visit.
I lived in Dubai for three years. I would strongly suggest not wearing shorts there. It is accepted in the malls and at the beach, but you will stand out and it looks tacky. Jordan would probably be a better choice… or Western Turkey.
I assume post #11 was not in response to post #10, right? 
Lol! No!
Another vote for Israel. I was at the beach today… Skin Cancer Central! :eek:
The “Neutral Zone”? Not much happening there.
Jordan is definitely safe. Aqaba is nice and quiet, Amman is busier, both were not what I’d call holiday paradise. Bahrain is OK if you’re up for an ‘alternative’ (lots of working girls, strip clubs, nightclubs) type of holiday and is safe-ish, plus you can basically get anything there if you have the cash. I’ve had fantastic holidays in Egypt, and sailing down the Nile, visiting various temples on an organized tour is more than great. Saudi is out - no tourists welcomed, which is a good thing IMO. Kuwait is very foreigner-friendly, hard to get booze (not impossible), you must dress appropriately apart from when on hotel grounds. Tunisia has recently made huge efforts into developing tourism and even attracts a lot of elderly people (my parents have been four times in the last few years), local drinks are very much available in hotels but not widely outside of them.
All have large Muslim populations but cultural ‘rules’ can vary between, and even in, countries. What is acceptable in one city may not be in another, so it’s best to be flexible and look around to see what’s the dress code when you get there.