Some third party systems offer a session management explicitly for this purpose.
For example, Google may require two-factor authentication if users set that up, and for apps (such as yours?) which do not support TFA, they either have app-specific passwords, or some sort of permanent session.
There may be more than one type, for example Stack Exchange sign in has SE requesting a small amount of data from Google, but they could get a lot more if the user allowed it. On the other hand there may be other APIs or long-term session possibilities that just require the user to re-enter their password when something concerning happens. (which is rare)
Each third party service (Google, Facebook, etc.) will have their own differing options here.
If you still determine that permanently storing a password is necessary, then yes, two-way encryption is the way to go.
AES-128 (or higher) is the recommended symmetric encryption algorithm to use. As long as the key is generated using a Cryptographically Secure (Pseudo-)Random Number Generator then it will not be practical for the attacker to brute force. So, the attacker will look for a way to steal the key instead.
Assuming your data is in an SQL server, simply storing the key outside of the database will at least give you coverage against SQLi attacks. Do not hard code the key in your application source code, but rather, place the key in a separate file, so that source code may be copied out to a test environment if necessary, and a separate (non-secret) key can be used for such environments.
However, this only protects you against SQLi and source code leakage. Other types of intrusion could allow the attacker to read files throughout the server.
Make sure your application (and the authentication system it relies upon) runs in its own user account on the OS and filesystem. The key file should not be readable by other users (you without sudo) or applications (e.g. sendmail) on the system this way. (i.e. set the keyfile permissions to 600 or 400 for UNIX-like systems)
Overall you should secure your application, and any services in this environment against all manner of attacks. This is the first line of defense. Any other suggestions here are safeguards to help reduce the impact of a successful hack.
It's always possible there will be a mistake, and an intrusion would reach the sensitive user account. (the one that accesses the key file)
It may be possible to segregate user accounts within your one application, but this gets complicated.
The final safeguard is to use the end-user's password and session to derive the decryption key. This I think is the most secure solution after you've covered the above points, but is complex to implement and is not compatible with an autonomous password reset feature.
