Best practice basics for Labels and DLPs to protect company data

Addressing your points in order.
1. You can use mail rules to block emails going out with certain labels on: - https://office365itpros.com/2019/12/16/block-outbound-email-sensitivity-labels/. Also as you mentioned DLP rules can be used to remove external shares from labelled files.
2. You could have a label for that department. For example "Legal" and restrict access to only that department via a dynamic group. Be careful not to get too many labels using this approach. Try for 3-5 core labels as you mention then one or two at the most for each department (scoped only to that department). If you want to share them with others then have a "sharing" (sub) label that allows the users to define who gets the label. You could enforce any nuances with mail rules and DLP.
3. How soon after publishing these did you try in Outlook Online? They can take up to seven days to apply fully, some functionality may come before others.
4. Exactly that, the recipients get the required permissions (do not forward or encrypt only).
5. Ensuring labelling is appropriate for each partner should work. If the labels are encrypted for one partner and somebody accidentally emails them elsewhere, the recipient isn't going to be able to open them. Again, be careful of too many labels. There could be some mileage in configuring mail rules to say if this label (ABC company label) goes to "XYZ company" then block it.