The main problem with riding in SA is that there is just far too much to do and see!
My personal favourite is Namaqualand (Springbok, Gariep) and the North West. There are red dunes past Uppington. You might be able to stay at one of the private lodges near to the Kgalagkadi Transfrontier Park. Unfortunately you can't ride into the parks, but you could arrange for one of the surrounding lodges to drive you in.
Golden Gate Highlands in the east is also superb - i think you can ride through there, as there is a public road through the park.
Oh, OK, in fact it's all superb.