From a military perspective, cloaking technology would be an enormous advantage for offensive, defensive and espionage purposes. No rational state would give it up willingly, and it was certainly within the Federation's technological capabilities to develop it.
This means the Federation gave it up unwillingly. I speculate that the most plausible reason the treaty was signed is that the Federation saw the Romulans as an existential threat. They gave up major concessions to avert a war they viewed as unwinnable.
For reference, here's the relevant chronology:
- 2266: Kirk encounters Romulan cloaking technology, something previously "considered only theoretically possible, due to the enormous amount of power required.". The device is flawed, and still fairly easy to detect
- 2268: Romulans perfect the technology, and Kirk obtains a working cloaking device. The device can be run off the Enterprise's power generation capabilities
- (by 2269): Klingons have cloaking technology.
- 2286: The Federation obtains a functioning Klingon cloaking device in the events of Star Trek III and IV.
- 2293: The events of Star Trek VI take place. Praxis explodes, leading to peace overtures and the Khitomer Conference / Accords. By this point the Klingons had developed an enhancement to cloaking technology, allowing them to fire while cloaked (this technology must have proved dangerous, or perhaps been banned in the Khitomer Accords, since it wasn't later used.)
- 2311: The Treaty of Algeron is signed after the "Tomed Incident", which "was a terrible confrontation between the United Federation of Planets and the Romulan Star Empire in 2311 that cost thousands of lives.". In one of the books, this was apparently a staged event by Star Fleet intelligence to avert a larger war.
- 2344: In the Battle of Narendra III, the Klingons are betrayed by the Romulans, and the Enterprise C aids them. This leads to an alliance between the Federation and the Klingons. Note that in the alternate timeline, a war with the Klingons takes place, which The Federation was badly losing by 2366.
- 2358: The USS Pegasus tries a test of dangerous "interphase" cloaking technology. Unlike ordinary cloaking, the technology allowed ships to be completely undetectable.
- 2368: The Romulans attempt a partially successful test of interphasic cloak. They abandon the technology.
- 2370: The existence of that the Pegasus test is discovered and publicly revealed by Picard.
- 2371: An amendment to the Treaty of Algeron is made, which allows the USS Defiant to use a Romulan cloaking device while in the Gamma Quadrant. The device is subsequently used in the alpha quadrant on several occasions in violation of the treaty.
- 2372-73: The Klingons fight a major war with Cardassia.
- 2373: The Dominion War starts.
- 2373: Rom mines the entrance to the wormhole with cloaked mines.
- 2374: The Romulans are duped into joining the Dominion War by Sisko.
- 2375: The Dominion War ends.
- 2395: Date of the alternate timeline in "All Good Things...". In this timeline, the Federation regularly uses cloaking technology, presumably since the Klingons took over the Romulan empire, voiding the treaty.
From the chronology above, you can reconstruct what the balance of power was over time. At the time the treaty was signed, the Klingons and Romulans had a nonaggression pact in place. The Klingons had been severely weakened by the events at Praxis 18 years earlier, which had significantly shifted the balance of power in favor of the Romulans. Given that in the alternate "Enterprise C" timeline, the Klingons were still able to defeat the Federation, in 2311, the Federation must have been badly outgunned.
Additionally, the excellence of Romulan cloaking technology would allow them to use execute genocidal weapons of mass destruction, say by mining the Terran system with cloaked mines or destroying all life on Earth. One can imagine that the Tomed Incident was such a terrorist attack by the Romulans. (Accepting the non-cannon book above, a terrorist attack orchestrated by Starfleet Intelligence, presumably Section 31. They must have realized how badly the Federation was outgunned, and sought to force hardliners to the negotiating table by showing Romulan military superiority, as the US did with Japan in 1945.)
In this theory, the Romulans were afraid the Federation would become a military threat, and were willing to completely annihilate them (including their old enemies, the Vulcans) to prevent it. The Federation was presumably presented with an ultimatum: "cease development of military technology we view as degrading our absolute military superiority to you, or we will conquer the Federation entirely." There were presumably territorial concessions made along the way as well. The Romulans would have felt safe doing this due to their nonaggression pact with the Klingons. No one would stand between the Romulans and domination of the Federation.
Between the Treaty of Algeron and the end of DS9, the balance of power shifted. The Romulans became overconfident, and broke their nonaggression pact with the Klingons. This led to an alliance between the Klingons and the Federation, meaning that the Romulans no longer had absolute superiority.
At this point, in the event of a war with the federation, they would be able to quickly outfit their ships with state-of-the-art Klingon cloaking devices, significantly reducing the Treaty's force. The treaty remained in place, preventing war in the short term, but the Federation began to seek ways of getting out from under its yoke. They developed gravimetric scanners, which meant that the Romulans would no longer be capable of executing a fully surprise attack. They developed better weapons, to the point where their flagship was at least a match for a Romulan warbird. They were still outgunned, but not as badly as they had been.
They attempted to develop cloaks so flawless they could run them without the Romulans knowing they were in violation of the treaty (interphasic cloak). Eventually, the war with the Dominion took precedence, and the Federation began using cloaking more openly, culminating in the cloaked mining of The Wormhole, a major violation of the treaty. The Romulans didn't care, since defeating the Dominion was a higher priority.
That the Federation started using cloaking technology when they were more of an equal to the Romulans militarily is further support for this theory. The treaty existed because the Romulans could credibly claim to be able to force compliance on the Federation if needed. Once that superiority ended, the treaty started to crumble.