For your background, I would recommend the following first:
Classical Mechanics by Taylor
Classical Electrodynamics by Griffiths
These should be relatively easy for you given your stated math profile, but you'll learn a lot with relatively little suffering. Once you are done with those (or at least with the "required" chapters in each) you can move up to more difficult material, such as:
Classical Mechanics by Goldstein AND/OR Landau (yes, CM again)
Modern Electrodynamics by Zwangwill OR Classical Electrodynamics by Schwinger (yes, ED again)
Principles of Quantum Mechanics by R. Shankar
Statistical Mechanics in a Nutshell by Peliti
These books above cover a pretty good basic core for graduate physics. There are many more specialized or advanced topics that may interest you. If you're thinking of astronomy/astrophysics, then a pretty handy book to have is:
An Introduction to Modern Astrophysics by Carroll & Ostlie (I used this one extensively for my Master's)
Also, you can use the following as mathematical supplements:
Basic Training in Mathematics by R. Shankar (great for "understanding", i.e., knowing what you're doing mathematically, though very informal)
Mathematical Methods in the Physical Sciences by M. Boas (great for "doing", i.e., practicing until you can do things automatically)
Physical Mathematics by Kevin Cahill (graduate level, for use only after you percieve the previous two as "too basic" or "not rigorous enough")
The following are short, succint, modern (and sometimes quite advanced) books by Cambridge Press that cover many of these topics:
A Student's Guide to Vectors and Tensors
A Student's Guide to Maxwell's Equations
A Student's Guide to Lagrangians and Hamiltonians
A Student's Guide to Entropy
There may be more books in this series that I'm not aware of.
Obviously, if you're on a budget, you'll have to prioritize, find used books, search the library, etc.