Go on....
I know all the guys I've met from Manaus are tough, but I thought Rio was generally regarded as the top place in Brazil.
I disagree with Fernando. Manaus have great guys indeed, but rather because it has many guys that make out of jiu-jitsu their living. It is a poor state and you have many social projects, therefore you have many guys that grew training jiu-jitsu as there main chance of getting a better life. If you want to train with intensity and you are looking more for good partner rather than high level teaching you should look for academies in less wealthy places, such as Cicero Costa in Sao Paulo.
I consider Sao Paulo, Rio de Janeiro and Manaus the best places for training BJJ. In Rio you still have many old school senseis and a high concentration of great instructors, such as Rico Vieira (Leo Vieiras brother), Fernando Terere, Roberto Gordo (the academy is a few meters from CRs house), Carlos Rosado (Carlson Gracies Red belt), Jefferson Moura (GB HQ), etc. You probably wont find the same viarity in other cities, even though you will probably find BJJ academies almost anywhere you go.
Sao Paulo is great for training also, but depending on the academy you choose (such as Alliance) you will have to spend a lot of money. As I said before, the academies where there are social projects are the ones you will probably find the best training partners. You have Cicero Costa and Dida Jiu-jitsu as an example. If you go to Santos you can also get to train with Cavaca, Buchechas teacher.
If I were you I would choose Rio. You will be able to do a turistic visit and since Connection Rio is located here it will be much easier for you to organize your trip. I am brazilian and train under Gordo.