Three weeks in Brazil

The suggestion I have is to arrange your itinerary to be in São Luis at the end of June (for Sao Joao until the first couple of days in July) for the Bumba Meu Boi. It's a colorful folk spectacle that not many tourists have the knowledge or timing to be lucky enough to see.

"Nifty route" for that list = making flight reservations now.
No time for "anywhere else". Maybe cut Natal. Plenty of other good beaches in areas on your list. (Sea beaches in São Luis are awful though.) See Rio for a few days (extend time and add side trip to Ilha Grande if you want, plan a day to get there and a day to return to Rio), fly Rio to Belo Horizonte for OP or bus via Tiradentes, then fly to Salvador and environs to see the city and do some day trips (3-5 days), then São Luis (2-3 days min, include a day to get there; see Alcantara, Raposa, the Reviver, and the Boi at night) and the Parque Lencois (2 days, try Santo Amaro) and to Fortaleza to fly out.

Yeah. Bumba Meu Boi (or Boi-Bumba, and a whole host of other names) is a must if you will be in the area around the end of June. The Bumba-Boi festival in Parintins is huge, but it is celebrated all over northern Brazil (and São Luis is supposed to be another highlight for this).

5 days in Rio is not enough to see Rio and Ilha Grande. Plan at least a week for this.
5 days for a jungle tour from Manaus is okay. Don't plan time in Manaus itself: the only things worth seeing can be done in a few hours/half a day.

Parintins is out-of-the-way for any continuation on your trip, so São Luis makes more sense for that. I would probably skip Salvador. It's a long way out of the way, and while a great city and with beautiful beaches nearby, the stretch between São Luis and Fortaleza should give you a good feel for the northeastern beaches. Unfortunately, I also don't see how you can fit in Ouro Preto in an itinerary Rio+Manaus+São Luis. 2 days in São Luis for the festival, 2 days in the Lençois, and 3 days in Jeri fills your 3 weeks, and there are some other beach towns along the way to Fortaleza that are also great.

Fortaleza itself has nothing to recommend it. I don't even like the beaches (praia do futuro is okay, but nothing spectacular: Rio's city beaches are a lot nicer).

In São Luis, the festival is called by the designation, Bumba Meu Boi, or more simply "O Boi".
What is called Boi Bumba in Parantins is a crowded, frenetic, commercial presentation in a large arena full of domestic tourists.
In São Luis, there are various venues from a small street in front of a home for the elderly to the SESC complex to a purpose built exhibition area, but much more folk-y and accessible. The celebration in its roots version, with traditional drumming, can also be seen in Santo Amaro, next to the Parque.
"The stretch between São Luis and Fortaleza" in no way resembles the area around Salvador, and the culture is almost totally different. With limited time and a fixed outbound flight, I would suggest flying from São Luis to Fortaleza, since transport in that part of the world often does not run on schedule.
Salvador is unique in the extent of African culture that survives and is openly displayed; it is a " don't miss" for sure. There will also be São Joao festas around Salvador, and a huge all night forro festival in nearby Colonial Cachoeira on the day. There is sufficient variety of beaches to please.
These events provide an opportunity to see traditional Brazilian culture mostly as yet undiscovered by foreign tourists.

On the other hand, a typical, brief Amazon trip out of sprawling, ugly, boring Manaus is likely to be superficial. Perhaps save the Amazon for a future trip to Peru.

The festas juninas in Salvador aren't much to right home about if truth be told. If it's the OP's first trip to Brazil, I suppose they might be. The biggest, if not the best is in Caruaru in PE but that's going out of the way, especially on such a short trip.

There's an immensely amusing alternative in Estância about a four hour bus ride north of Salvador or an hour or so south of Aracaju. All night forro plus an amazing display of idiots hurling grenade sized fireworks at each other and propelling them along a wire ( barco do fogo) plus the all female bloco that parades down the main streets. Google barco do fogo for some videos. Bit easier to et to than Parantins, you can do it as an overnighter from either Aracaju or Salvador. You can guarantee you won't see another foreign tourist, if that's a point of appeal.

Five days is not enough time for Rio and Ilha Grande. Aim for a max of two maybe three spots . Choose on the basis of what interests you.

I wasn't trying to imply that the coast of northern Bahia and the coast of Maranhão/Ceará are the same, just that you will have a good share of beautiful beaches on both stretches.

I also disagree that flying from São Luis to Fortaleza makes the most of that trip. It's a fairly well-travelled tourist route to go from São Luis to the Lençois, and from there on to Jeri and Fortaleza. There's a public bus which isn't hard to connect, and there are tourist excursions which do the Jeri-Lençois stretch in 4x4 and boat along the coast. You should absolutely leave a margin in case of transport delays between arriving in Fortaleza and the flight, but you could leave that margin in Jeri if you are able to pay for private transport, which can be organized to take you straight to the airport. Or you could plan an extra stop nearer to Fortaleza (Lagoinha, for instance), from which it is also easier to plan transport to the airport.

As for the choice of Manaus and a jungle trip, that's really up to the OP. While the jungle lodges around Manaus don't have the same opportunities for spotting large mammals as a few thousand miles further upriver, there's plenty to see and do. In 3 weeks the OP is necessarily going to have to pick and choose his destinations. Salvador is definitely a top spot, as are the colonial towns of MG, but if the OP is more interested in natural beauty than culture, you could do a lot worse than the Amazon. If wildlife is the aim, though, I suggest the Pantanal rather than the Amazon around Manaus.

5 days in Rio is plenty (I always suggest at least 7 days there). You will need more if you want to take in Ilha Grande for a few days.

Fly to Manaus from Rio (that wont be cheap no matter what). Then work out what you want after that. Head to Sao Luis and Lencois or go down to Fortaleza/Jeri or spend a week down around Bahia (plenty of great attractions not far from Salvador).

Thank you all for your replies and advice.
Manaus is pretty out of the way, however I'd really like to go trekking (24+hours) at some point, anyone have any other suggestions that might work for the following itinerary?
- Rio, inc trip to Ilha Granda, 7 days
- Fly/coach to Belo Horizonte, 4 days
- Fly to Salvador, 4 days
- Fly to Sao Luis (skip Belem), 4 days
- Coach via the lencois to Fortaleza, 3 days
...thoughts?

Ilha Grande might not be very good at that time of year. It is 'winter' so might be cooler than usual. I wouldn't worry too much about it but you can explore the coast of Rio pretty well - lots of places.
BH - there is very little of interest to warrant a 4 day visit. Spend that in MG cities like Ouro Preto and Tiradentes.
If you want some trekking head inland from Salvador to Chapada Diamantina and do some overnight/multiday stuff there.

Agree on the trekking in Chapada Diamantina.
The Minas Gerais part could include Tiradentes and Ouro Preto in 3 days, not 4.

The last part done in 3 days does not give time to visit Jericoacoara, or leave any for delays (I speak from personal experience on what can happen up there in the park area.) It's at least 2 days from Barrerinhas to Jeri by private transport, and more by bus/ ferry, and another day to Forteleza direct. I strongly differ with the idea that it is now "a fairly well traveled tourist route" from the Lencois to Jeri. in such a short time after it was almost impossible to get any info at all about the area in English or Portuguese. Private transport is expensive, esp for one person. Buses/ ferry risk delays/ schedule changes. Again I would not leave so little time to get down that stretch of coast if I had an international flight at a fixed time at the end.