diplo ideas are really good. Seems like you usually have extra diplo points, so getting more diplomats and being able to field +2 relations early is key.
The new system confused me a bit until I realized you can have multiple "agreements" with a nation and it only counts as +1 relationship. (royal marriage, alliance, vassal, military access on the same nation only equals +1 relationship)