I'm glad that you were able to resolve your issue and thank you for posting your solution so that others experiencing the same thing can easily reference this! Since the Microsoft Q&A community has a policy that "The question author cannot accept their own answer. They can only accept answers by others Opens in new window or tab", I'll repost your solution in case you'd like to "Accept Opens in new window or tab" the answer.
Issue: End users are not redirected to Terms of Use but getting error:
error:invalid_client
error_description:Invalid redirect_uri https://login.microsoft.com/common/federation/OAuth2ClaimsProvider
Solution: The authority endpoint for TOU used was "login.microsoft.com/common" endpoint, once login.microsoftonline.com/common was used, users were redirected to TOU.
If you have any other questions or are still running into more issues, please let me know.
Thank you again for your time and patience throughout this issue.
Please remember to "Accept Answer" if any answer/reply helped, so that others in the community facing similar issues can easily find the solution.
Thanks,
Akshay Kaushik