The creation of orcs and trolls ties in with the fall of Morgoth and his betrayal of Iluvatar. The reason Morgoth, or Melkor as he is also known, broke away from the Valar and Iluvatar before fleeing to Middle Earth was simply down to his jealousy of Iluvatar. It was no secret that Melkor was the greatest of the Valar and he came to covet Iluvatar's power. Morgoth desired the ability to create which was something Iluvatar kept secret and Melkor was angered by the fact that anything the Valar created, including the music of the Ainur, did itself stem from Iluvatar.
As such, when Morgoth finally fled to Middle Earth and came into conflict with the elves, who were the first children of Iluvatar, Morgoth decided to corrupt and mutilate the elves to fashion them to his own purposes. Because he was unable to create anything himself, Morgoth created orcs from these elves to stand as a mockery of Iluvatar. Effectively Morgoth decided the best way to hurt and oppose Iluvatar was to corrupt that which Iluvatar had already created and use it to destroy more of Iluvatar's creations.
The exact origins of trolls is not clear, but it is likely that either Melkor did something similar to that which he did to create orcs or simply used his influence to corrupt trolls. Regardless, Treebeard's theorising amounts to no more than a theory based on his own understanding. Treebeard (who's Quenya name is Fangorn) is one of the oldest beings in Middle Earth, having been born during the Years of the Trees, and so he, like others, has likely heard the stories of Melkor's corruption. He would have come to understand that the orcs were a mockery of elves and upon seeing trolls, their size and their evil manner may have simply considered them to be a mockery of himself and his fellow ents. Since it isn't outside of Melkor's remit to do such a thing, it is quite a logical assumption to make, but it is purely an assumption based on Treebeard's understanding.
Given that this is Treebeard's viewpoint, he likely believes a creature made in mockery is inferior to that which it professes to mock. Tolkien often states that orcs by themselves are quite cowardly and weak leading them to form together for safety and they only attack in strength. Orcs are also afraid of sunlight, quite a considerable weakness, whereas their elven counterparts revere light. As a mockery, the orcs are presented almost as an antithesis to elves. From Treebeard's observation of the world around him, he likely sees similarities between ents and trolls and so has drawn a parallel to the relationship between elves and orcs.
As a previous comment stated, Tolkien himself did not consider Treebeard to necessarily be amongst the wisest of beings, despite his great age, indeed by the end of the Third Age, Treebeard, along with the other ents, largely live in seclusion from the world. They are reluctant to involve themselves in the War of the Ring and consider much of Merry and Pippin's arguments as stories or exaggerations. They also ponder on things for lengthy amounts of time and so Treebeard has possibly dwelled on the relationship between trolls and ents for some time. His basis therefore could simply amount to stories he knew of or heard from a world that has long since changed. Treebeard has taken a logical view in his assessment, but it is important to understand that he is disconnected from the world around him.
Now, relating to the strength of orcs and trolls against Legolas and Gimli, orcs and trolls, like every other creature, are unique. Not every troll is gigantic and ferocious. If we look at the trolls in "The Hobbit," though huge compared to Bilbo and the Dwarves, they are not excessively ferocious, instead they exhibit curiosity when examining Bilbo rather than immediate hostility and their talkative nature actually ends up being their undoing as Bilbo engages them in a conversation long enough for Gandalf to herald the light of dawn which turns them to stone. These trolls are not presented as intelligent beings and, though we do not see their military capabilities, they seem to be more reliant on their size than anything else.
Comparing those trolls to the Olog-Hai that took part in the Siege of Minas Tirith shows the latter trolls as being exceptionally cruel, vicious and deadly in combat. They were impervious to sunlight and intelligent warriors. They were also smaller in stature than other trolls, enough to warrant some to consider them to be giant orcs instead. So as we can see, there were many varieties of troll. Similarly there are differences between orcs. Although Tolkien used "Goblin" and "Orc" fairly interchangeably, there are differences between the goblins, as presented in "The Hobbit" and the orcs presented in "The Lord of the Rings."
Goblins are presented as intelligent but small and cowardly, in fact they seem to be of a similar height to dwarves. Orcs, though cowardly, aren't as cunning or devious as the goblins are noted to be, they also stand a little taller, being only slightly shorter than men. Uruk-Hai are then presented as standing around the height of a man. They are faster, strong and more fearsome than other orcs and capable of moving under sunlight without being weakened. Eomer himself remarks on the strength of the Uruk-Hai in comparison to other orcs.
So as we can see, orcs and trolls are incredibly varied. As for Legolas and Gimli, although they may not necessarily fall into the same class as a great warrior such as Glorfindel or Maedhros, (though this is perhaps down to how subjective you are), they were certainly skilled enough to face orcs and trolls in combat. Gimli was the son of Gloin and a member of the House of Durin. Such was his father's standing that Thorin Oakenshield had Gloin accompany him on his quest to Erebor. It would seem reasonable then that Gloin was suitably skilled in the art of war and would have imparted his knowledge to his son. As a member of the House of Durin, it is also likely that Gimli's family was positioned quite highly in Dwarven society, after all Gimli represents his entire people by taking a position within the Fellowship. This indicates that Gimli would likely be of enough standing that he would be trained in martial combat to a good proficiency. Elrond makes the nature of their quest quite clear and if Gimli believed he was lacking in combat proficiency he probably wouldn't have joined.
For Legolas, many of the arguments for Gimli also apply for Legolas, only in the Legolas' case he is quite clearly confirmed as being the Prince of Mirkwood. His father Thranduil was a warrior of decent ability given that he fought in and survived the Battle of the Five Armies (remember Thorin, who himself is regarded as a capable warrior, perished in this battle), whilst Legolas' grandfather, Oropher, led the Silvan Elves during the Wars of the Last Alliance. Though he and his people were considered strong, Oropher's haste got the better of him and he perished during the Battle of Dagorlad after refusing to follow Gil-Galad's supreme command. Whilst this does show Oropher was a poor strategist, he is still considered to be a capable warrior. Legolas being the son of the king would have received martial training throughout his youth and, given his grandfather's failings, would probably have had its importance impressed on him by his father.
Legolas and Gimli therefore, were well trained warriors, perhaps even being somewhat naturally proficient given their lineage. Also, out of the members of the Fellowship, each of the members (excluding the hobbits) are combat veterans. Aragorn was a ranger in the north for many years, he had also fought alongside Thengol (Theoden's father) whilst using the name Thorongil. Gandalf was one of the Istari and had been involved in the fight in the goblin tunnels as well as the Battle of the Five Armies, both of which he had survived and already displayed a proficiency in combat. Boromir was perhaps regarded as the mightiest man in Gondor, he had dedicated much of his time to improving his combat abilities and understanding warfare and even held the title of Captain of the White Tower. That title had not merely been given to him out of his position as son of the steward but he had proven himself a capable commander, being able to hold Osgiliath against Sauron's forces in the early days of the War of the Ring.
Each member of the fellowship had a proficiency in battle and out of all of them, Boromir, the proven battle commander, had been the only one of their number to perish. Thus Legolas and Gimli must have been very capable, highly skilled warriors, hence their ability in taking on and beating numerous orcs and servants of Sauron during the War of the Ring. Remember it takes more to make a warrior than simply swinging a sword around and hoping you hit the enemy harder than they hit you.
The final note to be made is the fighting style of orcs and trolls compared to elves, dwarves and men. Where the free people's are, for the most part, well trained and organised, the orcs are little more than a "mindless rabble." Orcs rely on strength of numbers and overcoming their enemies with a quick assault. Their typical ability in hand to hand combat would be akin to a Germanic tribesman, who is probably no more than a farmer by trade, fighting a Roman Legionary. They hack away at an opponent with ferocity rather than look for a weakness to exploit, trying to overbear them. Trolls similarly tend to rely on their strength and size rather than anything else. Against a well organised and disciplined group of soldiers, that will look for their weaknesses, they don't stand much of a chance regardless of how big and strong they are.