I am not saying it would be an easy win for a Galaxy class at all, just that I get the impression the Romulan Warbirds are overall inferior technologically speaking (not just talking shields and weapons, but all technology) to the Galaxy class ships and newer.
Again? Is this based on anything? The impression I've got is the opposite. The reason is that, when a species has inferior technology, they've taken care in the show to demonstrate this. For example, the Federation could read Cardassian transponder codes. I believe they flat out said that a Galor class was inferior to a Galaxy class (while describing it as still "top of the line."). Ferengi ships were definitely shown to be inferior (as their technology as a whole) in spite of initial speculation that they were equal. Romulans, on the other hand, were never shown to be inferior. Slower, yes, but that was pretty much it. Again, what's your impression based on?
it's reasonable to believe that the Galaxy class is more maneuverable than the Warbird, too.
I don't think it's reasonable to suggest either ship is noteworthy when it comes to mobility, especially when compared to Klingon Bird of Preys, the Defiant, etc. DS9 battles are usually the best indicator of mobility.
As for the cloak provision of the Treaty, if maintaining their cloak superiority is so important to the Romulans, for me at least, that tells me that they are very reliant on the Cloak to counter Federation ships. Conversely, that tells me that the Federation isn't worried enough about Romulan tech to object to having to give up the rights to cloaking tech. Put another way, unless the Federation was defeated by the Romulans during some war, and the Romulans dictated terms where the Federation had no choice but to abdicate rights to developing cloaking devices, then it seems to me that the Federation is confident enough that their technology is sufficiently superior to handle the Romulans, to not only allow the Romulans cloaks, but to feel they don't need to have cloaks, themselves. For example, during the Klingon Civil War, the Feds demonstrated they have the means to track cloaked ships.
The Federation gave up territory after fighting the Cardassians. They gave it up because they valued peace, not because they were defeated by the Cardassians. If anything, the technological advantage the Federation has over the Cardassians suggest that they could have imposed a unilaterally favorable treaty had they wanted to. It's just in their nature to value peace over conflict.
Now we don't know what happened in the Tomed Incident. We know that the Treaty of Algeron re-defined the Neutral Zone. We know it also prevented the use of cloaking devices. Perhaps the quid-pro-quo of territory change was favorable to the Federation (they did have peace with the Federation for 50 years and may have stayed that way longer but for the Borg attack on the Neutral Zone outposts). Perhaps they just valued peace more than the ability to use cloaks. Because they are predominantly explorers, the Federation prefers to not be cloaked (as Roddenberry put it "Starfleet doesn't sneak around"). If a war broke out against the Romulans, they can always equip their ships with cloaks (after all, given The Enterprise Incident, it seems that even Romulan cloaking devices are fairly compatible. Likewise, the Defiant was equipped with one without difficulty).
Given this, I'm not sure how much of a loss it was for the Federation to not routinely use cloaks. For the Romulans, however, they love cloaks. They also like to gain whatever advantage they can. Having the Federation not use cloaks, to me, is just preserving an advantage, not a sign of weakness. The Romulans are routinely shown as treating the Neutral Zone as their territory. They can patrol along Federation border with impunity because they're invisible. The Federation, on their part, generally stay on their side and enter as a last resort. The Treaty of Algeron could be seen predominantly as a negotiation over the Neutral Zone. To ensure the Federation doesn't enter, they can't have cloaks. It could be as simple as that.
during the Klingon Civil War, the Feds demonstrated they have the means to track cloaked ships
Yes, but they didn't know that when they signed the treaty. They did think there was a slight distortion from the cloak that could be seen (as the Klingon Bird of Prey could be seen in Star Trek III). It turns out they were wrong on that, because Romulan cloaks improved, but that was the belief. However, I don't think the ripple effect could track long-range anyway. Even now, the Romulans are invisible at warp as long as they stay under a certain speed (as seen in The Day is Cast). It's also worth pointing out that the tachyon net was very cumbersome and the Romulans figured out a way to disrupt it fairly quickly (suggesting the science capacity on a Warbird is nothing to laugh at).
I'd also point out, you first said that Romulan ships are weaker because they need the cloak provision to maintain balance and then follow that by saying that the Federation agreed to it because the cloak provision didn't give the Romulans much of an advantage. That's a bit of a contradiction.