Another good thing to do in combination with that is to store the SSO provider locally (cookie/local storage, whatever). Then simply use that instead of presenting the two step process -- you can default to the existing server-side determination if the method stored locally fails.
I don't mind doing the two-step dance once during first login on a new device, but having to deal with it every time is infuriating and lazy on the part of the company.