Where to begin with foundations of mathematics
There are different ways to build a foundation for mathematics, but I think the closest to being the current "standard" is:
Philosophy (optional)
Propositional logic
First-order logic (a.k.a. "predicate logic")
Set theory (specifically, ZFC)
Everything else
When rigorously followed (e.g., in a Hilbert system), classical logic does not depend on set theory in any way (rather, it's the other way around), and I believe the only use of languages in low-level theories is to prove things about the theories (e.g., the deduction theorem) rather than in the theories. (While proving such metatheorems can make your work easier afterwards, it is not strictly necessary.)
I strongly urge you to look at Goldrei [9] and Goldrei [10]. I learned about these books by chance in Fall 2011. Among foundational books, I think Goldrei's books must rate as among the best books I've ever come across relative to how little well-known they are. In particular, Goldrei [10] has been invaluable to me for some things I was working on a few months ago.
In case my personal situation could be of some help, in what follows I'll outline the approach I've been taking for what you asked about.
I too am trying to improve my understanding of ground-level foundational matters, at least I was this past Fall and Winter. (During the past few months I've been spending all my free time on something else, which is related to a subject taken by some students I've been tutoring.) I started with Lemmon's book [1], which was the text for a philosophy department's beginning symbolic logic course I took in 1979 (but I'd forgotten much of the material), and I very carefully read the text material and pretty much worked every single problem in the book.
After this I began reading/working through Mates [2], which was the standard beginning graduate level philosophy symbolic logic text where I was an undergraduate (but when I took the class, also in 1979, the instructor used a different text). However, I quickly decided that I was wasting my time because I had zero interest in many of the topics Mates [2] deals with and it was becoming clear to me that, after my extensive work with Lemmon [1], I could easily skip Mates [2] and precede to something at the "next level".
I then began Hamilton [3]. I got through the first couple of chapters, doing all the exercises (propositional logic), and then I decided to take a temporary detour and study a little deeper Hilbert style (non-standard) propositional calculus before continuing into Hamilton's predicate calculus chapter. I spent about 10 weeks on this, and have a nearly finished 50+ manuscript on how I think the subject should be presented, motivated by what seems to me to be major pedagogical shortcomings in the existing literature, especially in Hamilton's book. (Goldrei [10], which I didn't discover until later, is an exception.) In this regard, see my answer at [11]. However, at the start of the Spring 2012 semester I had to stop because some students I was tutoring in Fall 2011 wanted me to work with them this semester in a subject that I needed a lot of brush-up with (vector calculus). (I work full time, not teaching, so I have a limited amount of free time to devote to math.)
My intent is to return to Hamilton [3], a book I've had for over 20 years and have always wanted to work through. After Hamilton's book, I'm thinking I'll quickly work through Machover [4], which should be easy as I've already read through much of Machover's book at this point. After these "preliminaries", my goal is to very carefully work through Boolos/Burgess/Jeffrey [5], a (later edition of a) book I actually had a reading course out of in Spring 1990 but, due to other issues at the time, I wasn't able to do much justice to and I feel bad about it to this day.
After this (or perhaps at the same time), I intend to very carefully work through Enderton [6], a book that was strongly recommended to me back in 1986 when I was in a graduate program (different from 1990) with the intention of doing research in either descriptive set theory or in set-theoretic topology, but I had to leave after not passing my Ph.D. exams (two tries).
I have several other logic books, but probably the most significant for possible future study, should I continue, are Ebbinghaus/Flum/Thomas [7] and van Dalen [8]. Each of these is approximately the same level as Boolos/Burgess/Jeffrey [5] and Enderton [6], but they appear to offer more emphasis on some topics (e.g. model theory and intuitionism).
Everything I've mentioned is mathematical logic because set theory (naive set theory, at least) is something I've picked up a lot of in other math courses and on my own. What I'm really looking for is sufficient background in logic to understand and read about things like transitive models of ZF, forcing, etc.
[1] E. J. Lemmon, Beginning Logic (1978)
http://www.amazon.com/dp/0915144506
[2] Benson Mates, Elementary Logic (1972)
http://www.amazon.com/dp/019501491X
[3] A. G. Hamilton, Logic for Mathematicians (1988)
http://www.amazon.com/dp/0521368650
[4] Moshe Machover, Set Theory, Logic and their Limitations (1996)
http://www.amazon.com/dp/0521479983
[5] George S. Boolos, John P. Burgess, and Richard C. Jeffrey, Computability and Logic (2007)
http://www.amazon.com/dp/0521701465
[6] Herbert Enderton, A Mathematical Introduction to Logic (2001)
http://www.amazon.com/dp/0122384520
[7] H.-D. Ebbinghaus, J. Flum, and W. Thomas, Mathematical Logic (1994)
http://www.amazon.com/dp/0387942580
[8] Dirk van Dalen, Logic and Structure (2008)
http://www.amazon.com/dp/3540208798
[9] Derek C. Goldrei, Classic Set Theory for Guided Independent Study (1996)
http://www.amazon.com/dp/0412606100
[10] Derek C. Goldrei, Propositional and Predicate Calculus: A Model of Argument (2005)
http://www.amazon.com/gp/product/1852339217
[11] Proving $(p \to (q \to r)) \to ((p \to q) \to (p \to r))$
"...mathematics is so rich and infinite that it is impossible to learn it systematically, and if you wait to master one topic before moving on to the next, you'll never get anywhere. Instead, you'll have tendrils of knowledge extending far from your comfort zone. Then you can later backfill from these tendrils, and extend your comfort zone; this is much easier to do than learning "forwards"."
-Ravi Vakil
Even though this might not be directly relevant, it might be another opinion on the matter. For what it is worth, I think my mind works like this.
http://math.stanford.edu/~vakil/potentialstudents.html This page has many more nice ideas.