I'm kind of in a similar situation myself.
Years ago I studied Math and CS. Of course, I spent most of my time studying more CS friendly math. I could 'prove' my away around any physics major. However, my background in applied analysis was a little weak. I'm going back to school and take some undergrad physics courses.
The biggest problem you'll face is doing physics problems. It's not the actual calculations. It's not understanding the physical models. It's just doing the calculations. It's this wierd phenomenon of setting up the calculations using physics knowledge. I've heard it described as 'physical intuition'. Frankly, doing a lot of problems in mechanics has help greatly.
I've found Sears and Zermansky to be kind of lacking for introductory material. It's not bad, just kind of synthesized. I like David Morin's introductory mechanics book instead. His book was designed for a freshman level mechanics course, but it actually introduces the Euler-Lagrange equation and some action physics as well. Very cool. Also, his lecture notes give some great insight into doing physics. I've also found 'Electromagnetic Fields and Waves' by Vladimir Rojansky to be of great help as well. It's a cheap Dover paperback and is designed as a junior-level E&M text (i.e. only requiring a introductory survey knowledge of E&M).
I've also found the video lectures by Walter Lewin (i.e. physics I,II,III at the MIT OCW site) to be very helpful.
[download David Morin's mechanics book; w/ lecture notes and solutions to exercises]
[talk a look at his free 'Demystifying Quantum Mechanics' workbook and his related software]
[Rojansky's E&M book; the author had quite the reputation as a teacher at Harvey Mudd College]
My advice is go with your strength first. How comfortable do you feel with the Calculus of Variations/Advanced Calculus. Try looking at Morin's book or maybe Kleppner. If you can handle that, try looking at Goldstein. There's a good chance you'll be using that in a advanced ugrad/grad level theoretical mechanics course anyway. If that goes well, take theoretical mechanics. Heck, most physics majors have problems grappling with all the 'applied math' in a mechanics course.
P.S. Incidentally, try talking to some professors in a physics graduate program. Most physics departments respect people with an advanced math background. Also, you'll have to try multiple departments. Some react better than others. Surprisingly, the better departments treated my inquiries more seriously than the 'lesser' departments. Go figure.