Which first? Agile or Scrum?

Scrum is one of many agile frameworks.  There may also be agile methodologies, but scrum is not one of them.  

This sites scrum master learning path includes the agile manifesto as well as its 12 principles.  It also lists some good books that you may or may not wish to read. 

I'm not aware of any "agile methodologies" certification, and if I came across one, I'd be suspicious of its quality. Agile is not a methodology, but rather a set of values and principles. One of the earliest forms was Agile Software Development, but the underlying concepts have spread to other fields as well. It was created as an abstraction over the key ideas that worked from a number of different methodologies and frameworks - Extreme Programming, Scrum, Crystal, DSDM, Adaptive Software Development, and more.

If you're looking to start transition from traditional project management to some form of agile coaching, a certification would probably help get past HR screenings. The only question is which methodology and training to take. Since your objective is to make a career transition, I'd recommend spending some time to search for jobs with the titles "Scrum Master" and "Agile Coach" in your area (or, if you want to relocate, the area where you want to go) and look to see what certifications are most requested. Some companies are (wrongly, in my opinion) sticklers about which organization their people are certified through. If you also opt into training, you should learn more about the trainers and their backgrounds, since not all trainers are equal.

If you want lower cost resources to get you started, Scrum.org has a Scrum Master learning path and lot of high quality blog posts to get you started. I can also recommend the book Coaching Agile Teams: A Companion for ScrumMasters, Agile Coaches, and Project Managers in Transition by Lyssa Adkins. These will give you a taste of what you need to know with a minimal cost investment to make sure that it's definitely a path that you want to go down.

Good luck.

Good information.  Thank you! 

Thomas:  ScrumAlliance (which from what I gather is top two most widely accepted Scrum certification organization along with Scrum.org) offers the Agile Leadership I and II Certifications.  Towards the bottom of this page:   https://www.scrumalliance.org/get-certified    You are correct, they are Agile Leadership, not Agile Methodology certifications.  What is your take on those?

And I am still not clear...  if someone wants to learn both Agile and Scrum, does it make more sense to start with one vs the other?  Or it doesn't matter?  Or when you learn Scrum you automatically learn Agile?

Thanks again.