I can't comment on whether arrivals have got worse in the last few months, but otherwise I must disagree with most of the advice about GRU. Most of the time it takes me about 15 minutes from getting off the plane to clearing customs, which is a good deal more efficient than most airports including GIG. Last time (in November) it was about an hour, but that's only because BA247 was two hours late - had it been only one hour late, it would have been the first plane of the morning and plain sailing.

I wouldn't be too worried about which flight you book. If you miss a GRU-GIG flight due to a late inbound, I'd be surprised if TAM or Gol were unhappy to rebook you on the next flight at no charge. Not everyone behaves as strictly as BA about this sort of thing - it's a much relaxed more American attitude to flight changes. Do make sure to use the helpful little check-in area for connections right after Customs - don't go upstairs to the main area.

Don't even think about taking the shuttle CDG-SDU unless you miss your connection and there's no availability from GRU for four or five hours. It will probably take close to an hour to get from GRU to CDG and in rain could take two. GRU is a long way out from the centre of Sao Paulo, whereas GIG is not so far out so you really don't gain much from landing at SDU instead of GIG. On the good side, if you really can't get a flight from GIG (unlikely) flights from CDG are frequent and cheap, even at the last minute.