Growing up in the American public school system, Columbus had quite a prominent position in the discussion of the "discovery of America." Now as a teacher in that same public school system, I can say that many schools have adopted a more "open minded" approach to this particular topic. As I always tell my students, there is evidence of Vikings (Ericson) coming to the Americas before Columbus... I've even read a few books on a theory that Chinese explorers might have come within a day or two from the coast of California before Columbus' time (not sure of that one myself, but the theory is out there). And as my students have pointed out; it's hard to say that anyone of these folks "discovered" America if there were already native people there.
Well, I'm a Mormon and we are taught in the Book of Mormon that the first settlers to this continent were the Jaredites, who came over when the Tower of Babel was built in the Middle East. The second group to come to the Americas was the Nephites, about 600 BC. The Lamanites split from the original group of Nephites and eventually wiped them out. Today's modern Native Americans are descendents of the Lamanites and were already here when all the European explorers came over.
I don't expect many people to swallow my beliefs, but it very clearly explains to me that all Indian tribes should get credit for "discovering" America. Europeans, and later the American people as a whole, never really gave the Indians their fair share of everything, never tried to understand them, and never honored them as the original stewards of this great land.
As a high school teacher, I have had many students come to me upset after learning that Columbus was not the first to discover America. These students feel mislead by their earlier education (teaching Columbus was the first). I tend to believe that no one really "discovered" America (given it was already inhabited when non-Americans came).
Generally, the earliest settlers in America are known as Paleoindians, and they came in waves, probably from different locations, as there are two or three distinct genetic patterns, broadly speaking, among Native groups. It is also possible that people from Polynesian islands came in contact with South American peoples before Columbus, and probably even before the Vikings. The thing is that America itself didn't exist before Columbus. It was a historical and geographical construct created by Europeans. The contact initiated by Columbus, whether a "discovery" or not, opened the door for the creation of a very different world than had previously existed on both sides of the Atlantic.
I think most people know that the first settlers in the Americas were not those who came with Christopher Columbus. There is evidence that the Vikings came earlier to places in present day Canada. In addition, there are some ideas that people came across the Bearing Straight during the Ice Age. Due to the fact that much has been lost due to time, we have to admit ignorance in many ways.
We believe that the first "Native Americans" made it to the Americas as much as 25,000 years ago. Given this fact, and the fact that these were not literate civilizations, there is no way to have any idea as to what the first people to come to the Americas called themselves. We simply cannot know anything much about those first colonizers.
In addition, there is also some fringe evidence that suggest the Portuguese were in the Americas before Christopher Columbus. Their role in the changing of the Line of Demarcation also gives a pretty good idea that they were aware of the new continent.
There is a lot of professional research out there indicating that the Vikings landed in North America long before Columbus did; some schools are adding that information to the curriculum now.
I don't believe anyone knows the name of the original tribe that first colonized the Americas; we don't even have a reliable date for that colonization at this point. Certainly they arrived long enough ago to give rise to a number of different groups of Native Americans, with distinctly different physiological traits as well as distinct traditions, languages and societies. Unfortunately a number of these groups have either vanished or been assimilated to the point of losing their native languages, which has made it difficult to trace their travels and ancestry.
Your question is an interesting one and not easy to answer, however, it seems that the US educational attitude is increasingly leaning toward a better intercultural understanding than in previous eras which means that students today are much more likely to hear about Columbus within a stated context.
He was the first "westerner" to sail to North America. The ideas of "first ever" and "discovery" are more likely to be contextualized, erased or filtered out today than they were years ago.