Columbus was commissioned by the Spanish monarchy on his voyage, thus it is understandable that a large part of the Americas was claimed by Spain. What was the Portuguese claim that made them the rulers of vast territories in South America, without any major confrontation with Spain?
The Portuguese naval expansion happened earlier than Spain, because Portugal ended its reconquista earlier, in 1297, with the conquest of Algarve (southern Portugal), while Castille would end Reconquista in 1492. The Portuguese Navy is founded in 1312 by D. Dinis I and some of the following kings kept investing in the Navy. The most important king for the naval expansion of Portugal was Joao I, who started the overseas expansion with the conquest of Ceuta (a city in Northern Africa, nowadays it's a part of Spain) in 1415, but earlier naval explorations had happened before (like the discovery of the Canary Islands in 1336). One of Joao I's sons was Henrique, known as Henry the Navigator for his sponsorship of the naval arts.
The Canary Islands is an important case, because even if it was discovered first by the Portuguese it was conquered by the Castillians and the Papal See recognized Castille (Spain) as its rightful ruler after a long legal battle (more than a century after discovery). The papacy was very important at those times as mediator between kings and source of legitimacy (you were only recognized as a king if the Pope said so, see what happened to the Burgundians trying to reclaim Lotharingia). According to an edict by Constantine I (the first Christian Roman Emperor) the Papacy had the sovereignity over all the islands of the world. Back then it was thought that all continents had been discovered and that the only new lands to be discovered would be islands. This came to be important later, at the Age of Discovery and, in another example, in Adrian IV giving the right to rule Ireland to the English kings in 1154 (Adrian was English).
So the Portuguese naval expansion happened earlier than the Castillian one due to having finished Reconquista earlier, but not that much earlier (the Castillians are going to compete with the Portuguese for ownership of the islands near Africa very soon after they're discovered, not only in the Canaries but in others as well). The first Portuguese targets are a continuation of Reconquista, North African cities like Ceuta, Tangiers, etc. But the Portuguese, with their ships that become better and better (invention of the caravels, the square sails, etc) discover new lands. Their objectives are many: spreading the Christian religion, trying to find Christian allies in their fight against the Moors (the legend of Prester John) and to discover a way to reach India and get the spice trade that was so lucrative to the Muslims and Venetians. So the Portuguese try to circunnavigate Africa and this effort takes about a century. On their way they discover new lands and new islands, like Madeira, Azores, Cape Verde and most of the African coast. In 1488 they finally are able to pass South Africa, with Bartolomeu Dias naming the place he passed Cape of Good Hope (Cape City nowadays). India would be reached properly only in 1497. To circunnavigate Africa and pass the Cape of Good Hope one technique was taking advantage of the sea and wind currents by going west instead of staying close to the coast, towards what is today Brazil (which wasn't known at the time).
As Portugal discovers new lands the Castillians come soon later and legal and actual battles happen over who has the right to tax what. The legal part of these battles happen most in the Papal See. At first the Papacy is neutral regarding this new conflict between Castille and Portugal, but after the 1450s the Popes start to put things into actual writing in a series of Papal bulls. The most important ones are Dum Diversas, Inter Caetera of 1456 and Æterni regis of 1481. The combination of these Papal Bulls make it so Portugal has the right to the lands south of the Gran Canary and the Castillians the right to the north of the Gran Canary. Portugal will focus efforts east and south in trying to get to India by circumnavigating Africa.
At first this seems good, but with Bartolomeu Dias discovering the technique that is needed to go over the Cape of Good Hope in 1488 and Columbus discovering new lands to the west in 1492, things changed. People thought the Americas were Asia, so technically the Portuguese could have a right to that (one of the Papal Bulls said the Portuguese kings had rights over lands from Cape Bojador to the Indies, and Columbus thought the Indies were near the islands he had discovered). The portuguese king readied an expedition to these new lands, but the Spanish kings then opened new negotiations. In 1493 Pope Alexander VI (the Borgia Pope, who was born in Aragon, Spain) writes the bull Inter Coetera. This divides all the undiscovered lands of the world in two, by creating a meridian that is 100 leagues west of the Cape Verde. Everything east of that is Portugal's, everything west is Spain's, except for all the lands that had been accounted for by Christian states until that (so the Canaries remain Spanish, for example).
The Portuguese aren't satisfied with that, due to the technique needed to bypass the Cape of Good Hope. So they and the Spanish negotiate on their own a new treaty, named Treaty of Tordesillas, in 1498. The Portuguese argue with the Castillians that it is to the Castillians benefit to extend the meridian further west, as this will give the Castillians some lands in known Asia (remember, now the Portuguese have reached India by their African route). The Castillians agree to that and the new treaty divides the world with a line that is 370 leagues west of Cape Verde. This line would officially get the Portuguese the right to lands that are part of nowadays Brazil.
When the Pedro Alvares Cabral expedition was sent to India by Portugual in 1500, they tried the new technique of going west before going south to pass the Cape of Good Hope, and with that they discovered Brazil. At first Pedro thought it was just an island, named Ilha de Santa Cruz (Island of the Holy Cross), but later expeditions would prove it was part of a big continent (Amerigo Vespucci would be in these expeditions, and his accounts are one of the reasons why the continent is named America). There's some historiographical arguments between those who think the Portuguese already knew about Brazil when they negotiated Tordesillas and others who think the official account of discovery by accident in 1500 is the true one.