The best POD for Paraguay: make Benigno Lopez be the president, as was the wish of Carlos Antonio Lopez, instead of his brother Solano. Or even better, make José Berges be appointed as president. Both were reformists and intelligent leaders, not stupid proto-totalitarians like Solano. Before him, Paraguay always explored well the divergences between Brazil and Argentina. When there was a rare moment when the government of the two countries had more aims in common than against each other (the liberal cabinet in Rio and Mitre in Buenos Aires), Lopez did the worse thing he could do: threatened both countries because of a war against a weak ally (the Blanco government in Uruguay). If he had remained quiet, not initiating a war against his two strongest enemies, soon the liberals would loose the power in Rio, the Conservative party would be in power again, and the relations with Argentina would turn to normality (i.e., competition and some occasional tension).
Whoever is the president, he would need to deal with Brazilian and Argentine interests. From Paraguay, Brazil wanted basically two things: the recognizing of the Brazilian-Paraguayan border on Apa River, and not on Branco River, as the Paraguayans wanted, and free navigation on Paraguay River, as a guarantee for Brazilian access to the province of Mato Grosso. The border claims I believe could be solved by some kind of agreement, maybe including the sharing of the lands.
The Argentinian claims over Chaco were more problematic, I believe, since they changed a lot. The first Argentinian proposal was a border on the Bermejo River, but is was rejected by the Argentinian Confederation in 1855. Then, before the war, there was another claim till the Pilcomayo. Finally, in the Alliance Treaty with Brazil, there was an article that said all Chaco till Bahia Negra should go to Argentina (giving the Argentines a border with Mato Grosso). Maybe the Paraguayans could convince the Argentinians to accept the first treaty.
For Uruguay, both countries wanted it independent. Brazil certainly didn’t want to annex it anymore (but, of course, wanted all commercial privileges possible), neither Argentina. At least no serious politician of both countries wanted it. In OTL, the war was started because Brazil invaded Uruguay to support the Colorados. Mitre supported the Brazilian action, but not with troops (he also didn’t want the Blancos in power). I believe that, without the war, if the Colorados manage to be in power, Uruguay would be more pro-Brazil, at least till the next civil war.