from the UK the cheapest that i've come across is the jumeira Beach hotel itself, they seem to do some pretty good package deals. Failing that get hold of Ian at Naish Dubai (Google 'em) he was very helpful to me on a previous trip. Bear in mind kiting in Dubai itself is restricted to one specific beach just north of the Jumeira Beach hotel, or drive down to Jebel Ali.
Hope this helps!
