Though Indians and white men had encountered one another prior to the Pocahontas tale that's retold in The New World, there was still innocence to lose, and that's the core of Terrence Malick's movie. You probably already know the basics, as told by Disney: Young Native American princess Pocahontas (played by newcomer Q'orianka Kilcher) falls for handsome English explorer John Smith (Colin Farrell, who sounds way more Irish than English), eventually becomes "civilized" and visits the royal court in London. History isn't clear on the specifics, mainly because the principal accounts of the story were told by John Smith himself, years after the fact, and were likely exaggerated to make himself look better. Malick seems to be primarily following the Powhatan tribe's version of events, combined with some elements of Smith's accounts.
Facts and plot points are somewhat irrelevant to Malick anyway; he makes tone poems rather than narrative films. Long takes that drift through streams and forests, voice-over inner monologues from multiple characters and people who show up without explanation or backstory are his stock-in-trade, but unlike his nigh-incoherent Thin Red Line, this movie isn't choppy or scattershot in its focus. For one thing, there are only three main characters, one of whom--Christian Bale's John Rolfe--doesn't even enter the story until the third act.
All this may sound daunting, and it is, a little. You know how people occasionally come out of epic movies like Malcolm X and The Return of the King and are all "Wow, that didn't seem like three hours at all?" That won't be the case here. The New World feels every bit of its two hours and 15 minutes (already shortened about 15 minutes from its original cut). It doesn't feel like time wasted though. Everything is a visual feast, comparable in spectacle and wonder to any of the CGI fests we've seen in the past year. (It's all the more impressive if you can appreciate how cool it is that most of the film was shot using natural light.)
At the heart of it all is an entrancing lead performance by the teenage Kilcher, whose only previous movie role was as an extra in Dr. Seuss' How the Grinch Stole Christmas. Playing the young girl known as Pocahontas (a name never spoken aloud here), and the Anglicized woman christened Rebecca that she eventually becomes, Kilcher embodies both free spirit and repressed soul, as the story commands. When she meets her inevitable fate, it feels like King Kong in reverse, with hairy man-beast Smith unintentionally luring a beauty from the savage jungle, toward a world in which she can no longer be herself and where she is exhibited as an exotic sideshow. It wasn't the Puritans--it was beast that killed the beauty.
Whether or not Pocahontas and John Smith were actually romantic is still a matter of some debate, though it's become the stuff of folklore. She was around 12 when they first met, though in 1607 her age would not have been any kind of barrier. It may be a problem for some viewers, however, knowing Kilcher is in her mid-teens and Farrell about twice that. There's no sex, but everything short of it is implied. Still, the overall feeling one gets is not one of leering in the vein of those people who obnoxiously lust after Emma Watson in the Harry Potter movies. With Kilcher's Pocahontas, the attraction is as much of the spirit as it is of her beauty, which is important because her looks do not fade when strapped into a corset, though the inner light certainly does.
Oh, and let us all rejoice that we can watch this tale told without that fucking "Colors of the Wind" song. Someone needed to take the story back from Disney, and we couldn't have asked for more than Malick.