If you take the buses in the cities' bus stations, you probably will not have problems concerning the quality of them. As for the safety regarding thieves and speeding buses, thefts sometimes occurs in interstate buses but are not really common. Speeding drives on the other hand are quite common.
Also, if you do decide to go by bus, consider that the distance between Belo Horizonte and Curitiba is much bigger than to Sao Paulo, which is still quite distant. You best option could be taking night buses from BH to Sao Paulo (around 8-9h), then go from Sao Paulo to Curibiba (around 6-7h). If possible, don't leave on a friday night to avoid traffic.
Otherwise flying is much faster and if you buy in advance not much more expensive, although you should also consider the costs of going to and from the airports, which are usually farther from the city's centres.
For other touristy cities that don't have airports, there are usually good to ok buses to get there. For some small towns you might have trouble going if you don't rent a car, but it's very unlikely you'll go to places like these.