For an excellent and demanding self-drive desert safari I would recommend www.offroademirates.com.
The Scot who runs it is fairly rough and ready but is very capable and knows the area (UAE) extremely well. You will need to have driven in the desert beforehand though or else have someone in the car who has and can give you some pointers!
The usual deal is that you rent a standard 4x4 from a local rental outfit (V6 or V8 petrol Land Cruiser - he will recommend the company) and he brings the necessary kit.
I did a Liwa expedition with him and the dune driving is frankly mind-blowing and on a par with the Ubari in Libya or Sossus Vlei in Namibia! You'll also see gazelle out there which makes a change from the Sahara.
The UAE is not cheap and the the above will cost you but the memory will be burned into your consciousness!
Alternatively if you want a backseat ride you can book a standard "night out in the desert" through your hotel which will normally include some exciting desert driving.