well I am going to add my (biased) review of all the books recommended above as i have experience with many of them:
First let me say that from what youre saying, it seems you are familiar with introductory calculus and linear algebra which is a great start, but you will find yourself confused very soon if you do not continue studying math along with your physics for the next several years.
MATH: you will need to get to a level where you are comfortable with vector calculus (ASAP), advanced linear algebra, differential equations, some real analysis, all of applied complex analysis, and then differential geometry at a minimum to be studying theoretical physics at the undergraduate level.
Spivak's Calculus: Fantastic rigorous study of calculus for those not yet ready for a true course in real analysis. If you don't consider taylor series to be something you were born understanding, this may be the book for you.
Spivak's Manifold Calculus: Rigorous introduction to what i classified above as differential geometry. This book will need a good solid grasp of real analysis before you try to tackle it so you will have to wait a while for this.
Rudin: Great books on real analysis but if you can understand them before taking an introductory course on real and complex analysis, my hats off to you.
Lang: Solid text on linear algebra but probably too advanced for an undergrad physicist to learn from since you very quickly need to develop a working knowledge of linear algebra and this book may bog you down with mathematical detail too long to achieve that. This may be good for a second study of linear algebra, the first time through i would recommend a simple linear algebra book such as Lay's linear algebra if you are not too confident or friedberg, insel, and spence if you really have a solid understanding of how pure mathematics works.
As for the other math concepts I mentioned, to get a quick introduction to vector calclus which you will DEFINITELY need, try "div, grad, curl and all that". Its a short and simple book but will give you a working knowledge of vector calculus as it is used in physics. Differential equations you will probably just pick up along the way. Complex analysis the choices are endless, just about any book on mathematical physics will cover what you need from complex analysis. I actually learned it from Complex Variables by Churchhill, this book is a classic and not too hard to understand. Differential geometry you will need to worry about after all the other things i listed are second nature to you, for this, depending on how quick you pick things up, you may be able to get away with just learning general relativity and picking up differential geometry as you go. If that is not your style, and you have a decent grasp of analysis at that point, you could try Spivak's introduction to differential geometry. (or of course his calculus on manifolds if you are a sado masochist)
PHYSICS:
Kleppner and Kolenkow: This is a book on basic mechanics but it studies the topic with a level of rigor that will prepare you for all the things you want to study afterwards. I really can't stress enough how helpful it was to force myself to learn mechanics from KandK as opposed to some simpler book for my future in physics. This book is genious, fantastic, words can't describe how good it is for a first physics book.
Purcell: I mentioned this book above, this is a natural choice to continue with electricity and magnetism after you have finished KandK. The value of this book is that along with teaching you standard EandM, Purcell is able to instill a physical intuition that I don't know where else I could have gotten. Even if you learn EandM somewhere else, this may be a good choice simply because of the great physical intuition that Purcell has and this book's ability to pass that on to the student.
Intro books like halliday, resnick, walker: Well the only two intro books I've had experience with is the halliday one and "University physics" by young and freedman. My recommendation would be to study from these books if you are having trouble understanding anything that is going on in kleppner and kolenkow, otherwise, forget they even exist. (In my opinion, halliday is better than the young and freedman book)
Feynman Lecture in Physics: This is a three volume set of lectures given by (arguably) the greatest physicist to ever live. Feynman understood things like no one else and if reading his lectures give you a little bit of that insight, you should thank the physics gods. The notes are from a 2 year series he taught at caltech that started from introductory mechanics and ended up covering just about everything you should learn from the first 2-3 years at a university. These books will not replace proper textbooks on the subject nor will they teach you everything you need to know about the subjects. What they will do is teach you to tackle physics problems and teach you to think like a physicist, and this might be more valuable than anything else.
Landau and Lif****z: this is a 10 volume set that is meant to be a rigorous study of just about every topic in physics. These are dense and not meant to be the book that you learn a topic from for the first time. However these are invaluable as a reference source. You should avoid these books until you feel you understand the topic that each of the volumes teaches about. Then you should open up the landau to realize how little you truly understand. (volume 1 is mechanics, volume 2 is classical field theory, volume 3 is quantum mechanics, volume 4 is quantum electrodynamics, and on and on)
Another thing i should add is that i have to disagree with serenity above, griffiths is a great physics writer and his books are great tools to study from. This is especially true for his book on quantum mechanics which in my opinion is the best book to begin learning quantum mechanics from.
Well hopefully you were willing to actually read through all that stuff I wrote and hopefully it answers your questions. Don't forget that physics is pretty hard and you have four years to get through what you need to learn as an undergraduate. In my opinion, it is better to spend more time but work through the proper books on a subject, rather than get frustrated and just assume that halliday, resnick, and walker, is what physics is all about, because that is just plain wrong.
)
