The mechanic told me Corollas made in the late '00s have this issue if the battery dies. Apparently certain settings are not stored properly on the computer and it forgets the correct idle if the battery dies or is disconnected for a while.
The story checks out because the issue started immediately after I replaced the battery cable (it spent a few days disconnected from the battery).
Now everything is fine.
Also had the battery replaced because it was leaking acid and it was 5 years old anyway.