Haffa (or Al Husn) Souk, only ten minutes' drive down pretty, tree-lined boulevards from the port, is massive and split into various sections. The spice souk -- heady with incense, staffed by mysterious black-burkha-clad women and wonderfully exotic -- is particularly worth seeing. Stalls selling Western gear and football shirts are rather more mundane, but there are lots of tailor's shops where you can get outfits made to measure and shipped to you.

The Al Husin Sultan's Palace, just around the corner from the souk, is the most spectacular of the three the sultan has in Salalah. It's not open to visitors, but it is lovely to behold, particularly the blue-domed roof of his private mosque.

The Corniche is a beautiful, long scimitar of golden sands. You can wear Western swimwear there, but you may feel naked compared to the modestly dressed locals. Overlooking the beach is a selection of cafes where local men go in the evenings to smoke bubble pipes filled with shisha (aromatic tobacco). Head inland from there, and you'll find the food market, which sells coconuts, dates and all things banana (including banana juice).

The Sultan Qaboos Grand Mosque, which lies between A'Suq Street and 23rd July Street, opened in 2009 and is a lovely building, resplendent in shades of cream, pale jade, green and gold. Visitor hours are from 8 a.m. to 11 a.m., and access is limited; women are allowed only into one area and, even there, should ensure that their heads, arms and legs are covered. It's worth a stop to admire the prettily carved ornamental windows on the building's exterior.

A trip down A'Salam Street, Salalah's 20-km-long main thoroughfare and a shopaholic's delight, will lead you to a wide range of goods for sale, including jewelry, perfume, books and the very latest computers and mobile phones. (The Omanis like their technology.)

Job's Tomb is a gold, white and blue edifice set high in the Qara Mountains, with spectacular views over the Jubriah Plain. A bus ride there costs only three Rials (a big savings, compared to the 20 Rial cab fare). But, there is a snag -- buses don't set off until they're full, so you could face a long wait. For cruise travelers, the best way to see Job's Tomb is as part of an excursion.

For real local color (and smell), pay a visit to the fish souk, worth seeing for the amazing variety of fresh-caught fish -- from gigantic halibut to red mullet and pomfret.

Take a tour around the UNESCO World Heritage sites associated with Salalah's frankincense trade. The most notable is Samhuram, which lies on the picturesque Khor Rohri creek. This ancient town dates from the 4th century B.C. and was at the heart of Salalah's frankincense region, so its ruins are surrounded by groves of fragrant trees. There, you'll also find the ruins of the Queen of the Sheba's Palace.