Just spent some time perusing early sci-fi on Wikipedia and heres some really interesting stories that caught my eye, also I just finished watching Cosmos again so everything will be painted by Carl Sagan influences.
If you want to go way back you could say that the Mahabharatha (400 BCE) was one of the first to see humans (King Ravti) depart the earth to some other far off place, in this case to meet the creator Brahma, then returns to earth to find many ages have passed, this might qualify better for the first time travel story.
Another really interesting example is in the lesser known part of Dante's Divine Comedy, Heaven (1472). Dante travels to the moons of all the (known at that time) planets in our solar system and meets humans who have in a sense, colonized those moons after death. Looking at this from a sc-fi perspective, (personal theorizing) death can be likened to a primitive understanding of the mechanism of travel between the planets, giving way to the dead people essentially colonizing these moons, quite interesting.
The earliest work really dealing with colonization by humans I found would be True History a satire that had aspects of colonization in it. It seems to lack impact though.
Perhaps a more fitting work would be The Martian Chronicles (1951) by Ray Bradbury, which deals with humanity having to colonize Mars in response to the approaching atomic destruction of Earth. This series was adapted into many different forms, movies, tv, and radio.
I would say that Heinlein wrote the most about colonization of other planets (Starman Jones, Red Planet and Farmer in the Sky), but perhaps Starship Troopers (1959) is the most fitting for "impact". This novels backdrop was humanity dealing with colonizing other planets and running into other (militant) races. This particular novel had a huge impact on a lot of modern sci-fi, for instance the first space marines, global government, mechanized warfare etc. In this novel colonization is more of a backdrop to deal with the issues surrounding humanity on a galactic scale, but if your going for impact, this is a good one.