During that 5-year period, what rights do I have with respect to the rest of Europe?
Non-citizen residents do have some rights but not the one you're most interested in (residence). For example, one that hasn't been mentioned is healthcare coverage, at least if you are affiliated to the national healthcare system and hold a European Health Insurance Card (EHIC). Or for another random example, the GDPR applies to you.
Can I live in other European countries, or is that only allowed for long-term residents and citizens?
To be very specific: You cannot reside in another European country on the basis of your Portuguese visa or residence permit.
The right to live or reside more than 90 days is still a national matter. There is a body of EU law that applies (freedom of movement rules, EU Blue card directive, long-term residence, procedural rules regarding refugees) but in principle each EU country is free to decide which third-country citizens get to live in the country or not. Even the long-term resident status is not a general right to reside anywhere in the EU (more on that later), freedom of movement only fully applies to EU citizens and their family.
Or would I still fall under the "90 days out of 180 days" rule?
Yes, this rule still formally applies. Visiting other Schengen (but not EU and in particular not Ireland) countries is one of the rights you gain through your status in Portugal but that's limited to short stays. At the same time, nobody is going to count whether you have stayed 89 or 91 days.
In my cursory research, I've seen some conflicting information on this topic, but a number of sources have pointed me to 2003/109/EC, and have suggest that EU residents must request a residence permit from another EU country if their stay is over 3 months. Is this correct?
Yes that is (roughly) correct (roughly because the threshold is not always three months but can also be 90 days, especially if you are not a long-term resident yet). The thing to remember is that while there are some procedural differences and even situations where EU law makes issuing a “permit” almost mandatory, third-country citizens should always get a residence document from the country where they want to live. Note that Directive 2003/109/EC is about long-term residents, not all residents.
If so, how easy is it to get such a residence permit? Is it substantially different from getting a residence permit as a non-EU resident?
No, it is not. In most cases, the same rules apply. How easy it is totally depends on your situation and the specific permit you are hoping to secure. There are many different permits in different countries.
And is there a difference in rights for EU residents vs. EU permanent residents?
The main difference is that it facilitates moving from one EU country to the next on a procedural level. So even if the rules governing the residence permit are still the same, at least you're not in the position to ask an employer to wait 6+ months for your visa to come through, you are allowed to move and figure things out after the fact and without having to deal with the often unpleasant visa bureaucracy.
It also gives you some protection if the move doesn't work out well. For example, if you move to say Spain on the basis of a work contract but after an accident you lose your job, your ability to work, and your right to stay in Spain, you can always come back to Portugal. But you won't have an automatic right to reside in Spain or immediate long-term status there (that will only come after 5 years in Spain, at which point you will cease to have the same rights in Portugal).
A small note on terminology (which can be confusing): “permanent resident” and “long-term resident” are not synonyms. In EU law, the term “permanent resident” is used for EU citizens, what we have been talking about is more properly called “long-term residence”. “Permanent residence” can also be used in national law or in English-language sources describing those but it can be defined differently so that the EU long-term resident and national permanent resident status are not equivalent.
