"The movie is more generous in showing what the visitors found here. Columbus encounters friendly Indians, of which one—the chief's daughter—is positioned, bare-breasted, in the center of every composition. (I believe the chief's daughter is chosen by cup size.)"
— Roger Ebert reviewing Christopher Columbus: The Discovery
In Rocket Girls, Matsuri is the first native to greet Yukari (since Matsuri speaks Japanese, unlike the rest of the Tariho tribe). Also subverted in that Yukari is actually also the chief's daughter, though by a different wife.
In X-Men, Ororo Munro/Storm's mother was Princess N'Dare, and her bloodline was the source of Ororo's white hair, blue eyes, and rarely-used talent for magic (which might have influenced her genetic mutation).
Ember goes through a classic trope-fulfilling phase once she reaches puberty. She starts dressing in a leather bikini, wants to meet boys from outside the tribe, and spends most of her time sulking and talking to her wolf-friend. Some years later, though, she becomes chief of her own tribe, and turns out to actually have leadership qualities.
Rahnee (who spends a lot of time rebelling against her father) Goodtree (who goes on a Vision Quest before she can properly become chief).
Shuna (chief Cutter's adopted human daughter, who tries really hard to be exotic and elfin when she starts meeting human men)
Vaya who dies in battle, but not before she finds a boyfriend outside the tribe and defies chief Kahvi's wishes.
Kahvi herself who didn't get along at all with her chief father Two-Spear and left the tribe in a huff
Venka Kahvi's second daughter, who... actually gracefully evades the trope.
Leetah herself. She's the exotic daughter of one of her tribe's two spiritual leaders, she starts her role in the plot being kidnapped by (and falling in love with) the white main character, and the entire first story arc is about two men fighting over her: the white hero 400 years younger than her, and the proud dark-skinned hunter she grew up with that she was about to get "engaged" to. Guess who wins. The trope is played with in an interesting way in that it's the hero's people who are the noble (and nubile) savages, while Leetah and her people are more civilized.
Violently deconstructed with Princess Nadkoko, who fits almost all elements of this trope... except the one who falls in love with her, Razorcat, is a disfigured, Axe CrazyBerserker serving as The Dragon to his Knight Templar mother. Cue to a Tear Jerker when his mother betrays Nadkoko's tribe and orders Razorcat to kill her, leading to a dilemma with Berserker Tears.
Marvel Comics Western hero the Ringo Kid was the son a white lawyer/rancher and a Comanche princess (never mind that the Comanche don't have princesses).
Tex Willer, Italian comic from Bonelli. Tex became chief of the Navajos after marrying the chief's daughter when she saved him from being killed.
Moon Fawn, who becomes the wife of Tomahawk. He first comes across her when she is bathing in a river and saves her from a bear attack. She falls in love with him and he has to prove his worthiness to her father, Chief Grey Elk.
Films - Animated
Pictured above: Disney's Pocahontas plays this trope pretty straight except Pocahontas is the protagonist herself. Also the other Powhatan are actually not that much less attractive than her (just look at Nakoma) and they are portrayed as having identical mindsets, emotions and intelligences as the English (white) settlers.
Peter Pan (the Disney version) featured Tiger Lily, who was rather more realistic in appearance as compared to the other (literally red skinned) Indians presented in the film. She was also far more attractive, to no one's surprise.
Kida from Atlantis: The Lost Empire played completely straight. While she is quite spirited, she doesn't do terribly much until she is merged with the crystal that powers Atlantis. She of course gets together with the first white boy she sees, Milo.
Plio (Aladar's adoptive mother) and her daughter Suri from Dinosaur. Her father, Yar, is actually the leader of the resident lemur clan.
In the direct-to-video sequel An American Tail: The Treasure of Manhattan Island, the daughter the Chief of an underground tribe of Native American mice named Cholena comes with Fievel and his friends to the surface to see if Europeans have become more tolerant. Sadly, they have not.
FernGully has Crysta, who is essentially Magi Lume's adopted daughter and apprentice. Crysta is the daughter of the fairy chief.
Films - Live Action
Ace Ventura: When Nature Calls plays this straight with the Wachati princess. She's one of the few members of the tribe who speaks fluent English, and offers herself sexually to Ace in gratitude for his assistance (he turns her down due to his vows as a Buddhist monk, but this doesn't stop him from furiously masturbating later).
It's heavily implied that he did end up sleeping with her at some point, as her new husband sicks both tribes on him when he attempts to consummate their marriage.
Shaft woos an African princess in the second sequel to his Blaxploitation hit. However she and her father were both educated in the West and act like it.
In Shanghai Noon, Jackie Chan's character gets engaged (married?) to the Indian chief's daughter somewhat by accident. But it all works out when she decides to elope with Owen Wilson's character instead.
In the film Stargate Daniel Jackson gets married to the Abydos chief's daughter.
In James Cameron's Avatar, the main character first meets Neytiri, the daughter of both the tribal and spiritual leaders of the Na'vi. The trope is even named outright.
Apache Gold: Nscho-tschi (Beautiful Day) is Intschu-tschuna's daughter and Winnetou's sister. Intschu-tschuna is the chief of Apaches and Winnetou his successor, and both are noble Indian men. Nscho-tschi is the cutest girl with big brown eyes and raven hair, and she's lovely, sweet and caring. She's also a bright girl with desire to go to school and learn as much as possible. She nurses captured Old Shatterhand to health and falls for him. Notably, she believes his claim that he saved Winnetou's life and she procures the evidence for him to prove that he's not lying. Old Shatterhand returns her affection but their love mostly stayed unresolved and undeclared.
Last Of The Renegades: Ribanna is not a straight example. She's the only daughter of the Cheif of Assiniboin tribe. She's a gorgeous woman and Action Girl who can fight because she thinks her father wanted a son. She falls in love with Winnetou, the Chief of Apaches. They plan to marry, but alas! Lieutenant Merril likes Ribanna and proposes he marry her — their marriage will cement a treaty of peace between white men and Indians. Most chiefs like the idea and promise not to fight if they do get married. Winnetou is shattered because he has fought his whole life for peace. He commits this Heroic Sacrifice, but he and Ribanna suffer terribly.
Codex Alera has Kitai, daughter of Doroga, leader of the Gargant clan of the Marat. Throughout the series, Kitai proves herself to be quite the competent fighter, easily able to hold her own against enemies that can overcome even the series' protagonist, Tavi. Doubles as a Green-Skinned Space Babe since the Marat are non-humans and literally flew to the planet in a spaceship, as opposed to the traditional humans who are the descendants of a magically-transported Roman legion.
Dragonlance has Goldmoon, whose status as "Chieftan's Daughter" gets in between her and her lover, Riverwind. It should be noted, however, that they are both from the same culture (plains barbarians).
Rukaiya in Belisarius Series is the daughter of an Arab sheik. In something of a subversion her dad is an urban trader and one of the most important merchant princes in the area.
Invoked with Val in A Song of Ice and Fire, the sister-in-law to Mance Rayder, the King-Beyond-The-Wall. Members of Stannis Baratheon's court regard her as a "wildling princess," despite the fact the the Free Folk have no concept of Royal Blood, and Val's relation to Mance doesn't affect her own status at all. Attempts to convince the southern nobles that an Arranged Marriage is incompatible with the wildlings Asskicking Equals Authority approach end in failure.
In one of the less spectacular Farscape episodes, John Crichton is stranded on an planet inhabited by an - apparently - primitive tribe of aliens. The daughter of the local matriarch is attracted to him, but he refuses her love knowing it will cause trouble in the tribe. The trouble happens anyway.
In the Star Trek episode "The Paradise Syndrome", Kirk suffers a bout of amnesia and ends up married to native Princess Miramanee. It does not end well.
It sometimes seems like every third Hopi legend/story/oral history involves a village headman's daughter (Hopis don't really have "chiefs") either as love-interest or protagonist. The heroes are Hopi too, of course, but Everything's Better with Princesses.
The Klamath Indians' explanation for Oregon's Crater Lake has a chief's daughter named Loha being the catalyst for the story. Her part comes when she turns down the advances of Llao, the god of the underworld, because he was... well, the god of the underworld. Llao decides to punish the people by making Mount Mazama erupt, but then the sky god Skell comes to the rescue. Skell imprisons Llao inside Mount Mazama and makes it collapse to seal the entrance to the underworld, forming Crater Lake. This story is loosely corroborated by geology, which tells us Crater Lake was formed when Mount Mazama collapsed into a caldera around 5677 BC.
Shania in Shadow Hearts : From the New World. She's the lead female character, love interest to the white protagonist, wears skimpy animal-skin looking clothing and dual wields tomahawks. Although she's not literally the daughter of a chief, she mostly follows this trope.
While Katara is the daughter of the chief of the southern tribe, she's never referred to as "Princess" and doesn't seem to have all that much interest in finding a husband. Her main priorities are learning how to Waterbend and helping Aang save the world (though he does have a crush on her and they get together eventually). However, this is mostly likely because the southern tribe isn't deeply into tradition, as the Northern tribe's Princess Yue most definitely plays this trope for all it's worth. The Southern Water Tribe appears to be democratic, while the Northern Water Tribe seems to be a Monarchy.
When Sokka tries to seduce Yue, he refers to himself as a Prince, but Katara asks "Prince of what?". For all practical purpose, being the daughter of the chief of a small, primitive town, doesn't give you a high rank outside, especially compared to The Chief's Daughter from a powerful kingdom.
This further expanded on in The Legend of Korra, where it's revealed that the Chief of the Northern Water Tribe is technically the chief of both tribes, despite the two being, for the most part, completely separated. Korra herself fits the bill in that she is the daughter of Tonraq, who is practically the Chief of the Southern Water Tribe in all but name, even though her uncle, Unalaq, is the chief of both tribes. At the end of Book 2, she fits the bill for real when the two tribes separate and Tonraq is officially elected as Chief of the Southern Water Tribe.
Pocahontas was the daughter of Algonquin Chief Powhattan note though technically not a princess since their inheritance laws worked differently, but stories of her romance with John Smith are greatly exaggerated. She was a preteen at the time, though it was not quite the strict disqualification at the time it would be today. The real John Smith wasn't exactly what you'd call a blonde Adonis. He was said to be a short, pudgy ginger. She did wind up with another English guy, John Rolfe. King James I took her 'royalty' so seriously he considered punishing Rolfe for his presumption in marrying a 'princess'.
Historical rumor has it that John Smith seemed to very coincidentally have Chieftan's Daughters fall madly in love with him in just about every native culture where he showed his face. According to his journals, anyway. There's some talk that what John Smith witnessed (if it really happened) may have been a ritualized ceremony designed to show newcomers who was boss (by nearly "executing" them and then having them saved by a little girl).