Balon Greyjoy clearly committed treason when he rebelled against Robert Baratheon. Why wasn't he executed, or stripped of his titles and forced to take the black? If Robert had appointed someone else as Lord of the Iron Islands he could probably be assured of the new Lord's gratitude and loyalty for a few years at least. Apart from yielding Theon as a hostage and having his castle walls destroyed, it doesn't seem like Balon suffered any punishment at all.
Robert's personality and principles
That is because Robert of that time and age was an honorable man who did not despise a foe for fighting against him if the cause was just.
"On the Trident, Ser Barristan here cut down a dozen good men, Robert's friends and mine. When they brought him to us, grievously wounded and near death, Roose Bolton urged us to cut his throat, but your brother said, 'I will not kill a man for loyalty, nor for fighting well,' and sent his own maester to tend Ser Barristan's wounds." He gave the king a long cool look. "Would that man were here today."
Not only this, Robert pardoned almost all the Lords who fought for Aerys Targaryen because he recognized that they were fighting for a cause that they saw as just and honorable. Back then, Robert was the living manifestation of chivalry.
Soon after Robert taking the throne, Balon Greyjoy rose in rebellion. GRRM has explained why did Balon consider it wise to rise against Robert:
He (Balon) believed that Robert, as a usurper, might not have the strong support of the other lords the way that a Targaryen king would have. He also thought he could defeat Robert at sea.
The year was 289 AC. Robert moved swiftly and his Wardens Tywin Lannister and Eddard Stark joined their levies to the Royal Forces. Stannis Baratheon commanded his brother's fleet and smashed the Ironfleet in naval battle.
Soon, the Royal Armies overran the Iron Islands and Walls of Pyke were smashed down.
So why did Robert do it?
The conversation between the defeated Balon Greyjoy and Victorious King Robert is recorded in TWOIAF:
The reborn Kingdom of the Iron Isles had lasted less than a year. Yet when Balon Greyjoy was brought before King Robert in chains, the ironman remained defiant. "You may take my head," he told the king, "but you cannot name me traitor. No Greyjoy ever swore an oath to a Baratheon."
Robert Baratheon, ever merciful, is said to have laughed at that, for he liked spirit in a man, even in his foes. "Swear one now," he replied, "or lose that stubborn head of yours." And so Balon Greyjoy bent his knee and was allowed to live, after giving up his last surviving son as a hostage to his loyalty.
TWOIAF: The Iron Islands: The Old Way and the New
So as evident, you can see that Robert did it because:
- Balon was correct. No Greyjoy had ever sworn an oath of allegiance to a Baratheon.
- Robert admired bravery and Balon was beyond a doubt brave.
- Robert admired the kind of spirit Balon had.
- Robert was chivalrous and admired good qualities in his foes.
What do the other Westerosi minds think on treatment of fallen foes?
Removing House Greyjoy or reducing Ironlslander power is a very bad idea because Cersei thinks almost the same way.
Robert should have scoured the isles after Balon Greyjoy rose against him, Cersei thought. He smashed their fleet, burned their towns, and broke their castles, but when he had them on their knees he let them up again. He should have made another island of their skulls. That was what her father would have done, but Robert never had the stomach that a king requires if he hopes to keep peace in the realm.
AFFC - Cersei VII
She is wrong however when she says her father would have done the same. Tywin Lannister was no fool. He explained his views on such matters to Joffrey.
"Be quiet, Cersei. Joffrey, when your enemies defy you, you must serve them steel and fire. When they go to their knees, however, you must help them back to their feet. Elsewise no man will ever bend the knee to you. And any man who must say 'I am the king' is no true king at all."
ASOS - Tyrion VI
Robert's rule was insecure. He wanted to win hearts of his vassals, not push them to the brink where they thought that any act against the usurper would lead to end of their status. This feeling only serves to stiffen the resistance. On the other hand, by issuing pardons you give your enemies hope that if they surrender, you are capable of forgiving them which leads to quicker surrenders. And generally, Pardoning people leads to winning their hearts permanently e.g. in case of Barristan Selmy and Lord Tyrell, it worked for Robert. Robert had also previously used his chivalry and charisma to turn Lords Cafferen, Grandison and Fell from Rebels to his Loyal bannermen.
In any case, Greyjoys are the most prestigious family in the Iron Islands. They were chosen by Iron Islanders to be their lords when Aegon I Targaryen conquered Iron Islands and ever since, they have ruled the Iron Islands and commanded their loyalty. Iron Islanders would take it as an insult to have their most prominent house destroyed.
It was simply a more beneficial political move in the long term.
Balon's people are much more independent and warlike, an outsider appointed by the king as their ruler would've had a hard time controlling them and could've caused them to eventually rebel. So, someone from king's court/circle was out.
Executing the king and replacing him with one of his family would not be much different from just keeping him. It could've been worse because there would've been nothing to leverage for assurance of his loyalty. Also, there didn't seem to be a good candidate around to replace him who would be guaranteed to stay loyal and be accepted by all.
But keeping his son hostage and letting Balon live achieved both stability (he couldn't rebel anymore for the fear for his son) and long term loyalty because his son (the future king) would grow up thinking of Starks as his brothers. A very smart move overall.