Any of the
Zona Sul shops (it's a chain of stores called Zona Sul, rather than any shop in the area defined as zona sul). Otherwise,
Deli Delicia is a high-end chain. There is no cheap champagne in Brazil; expect to pay well over the price you can get in Europe or the US.