Did a three week trip through SA several years ago. Landed Christmas day in Johannesburg. Started with a few days there which gave us a great foundation to understand the country. Second stop was Durban for a several days (which was fine, but could probably skip). Then flew to Port Elizabeth and drove to Kwandwe reserve. Amazing experience there. We had 6 drives over 3 days/2 nights. 1 day/2 drives we had bad weather and did not see much. The other 4 gave me enough pictures (elephants, giraffes, rhino) to last a lifetime -- especially the one drive we spent tracking and then up close with a lion. Then we drove the garden route with a couple nights in Knysna and an overnight in Swellendam. Also lovely. From there made our way to Stellenbosch for a few days (very nice) and ended with many days in Cape Town (great city).

Maybe Kruger and Victoria Falls will be overflowing with people (and even then my guess it is still worth it). The rest of the country has plenty of space no matter when you go. For us it was amazing trip and January was just fine. In terms of cost, outside of the safari which is pricey (but still totally worth it), I found everything to be really affordable and you get a lot of luxury and comfort for your dollar.