Having spent some months with a couple of (philosophy!) grad students on Shoenfield's first three chapters, I have to say that I agree with Smith's criticisms. Shoenfield is a great book, but it is extremely terse and it is sometimes hard to understand what the point of a certain proof is or why he is tackling a certain topic at that precise moment in the book. It seems to me better either in conjunction with a good instructor who fleshed out all that is happening there, or else as review after you have already read a couple of books on the subject.
So, what to read instead? Two books that I really like and that are much easier than Shoenfield (but also don't cover as much) are Richard Hodel's An Introduction to Mathematical Logic and Herbert Enderton's A Mathematical Introduction to Logic.
Hodel, in particular, has some of Shoenfield's flavor, so to speak, but with more detail. For example, he uses (what is basically) the same proof system as Shoenfield's, but has sections on alternative proof systems and several exercises that develop these further. I found his exposition to be amazingly clear, and he also has tons of really great exercises, ranging from the basic "check-your-understanding" variety to some that are mildly difficult (some of them are adapted straight from Shoenfield). On top of that, he also has a nice chapter on Hilbert's Tenth Problem (which asked if there is an algorithm for deciding whether a diophantine equation has a solution in the integers; the answer is negative). Finally, I also found his exposition of the technical details behind Gödel's theorems (specially the coding functions) to be very clearly done, better than in some other books I read.
Obviously, given that he is much more expansive than Shoenfield, he doesn't cover as much. For instance, Shoenfield's chapter on model theory explains not only compactness and related theorems, but goes as far as Ryll-Nardzewski's theorem on $\omega$-categorical structures, and in the exercises he also covers the ultraproduct construction as well as some applications to algebra (if I remember correctly). And Shoenfield's chapter on set theory goes as far as the forcing construction. Hodel, on the other hand, has only a small section on the rudiments of set theory, and his model theory is limited to compactness and the Löwenheim-Skolem theorems. But then again, if you're interested in those topics, you'd better served by reading first Hodel and then a more specialized book (say, Jonathan Kirby's recent introduction to model theory and Kunen's book on set theory).
As for Enderton, it is more straightforward than Hodel, I think. So whereas Hodel has two sections (and exercises) on alternative proof systems, Enderton sticks to his Hilbert-style axiomatic system and doesn't pause to show how things could be done differently. Also, Hodel is slanted towards computability, whereas I found Enderton a bit more algebraic (specially the exercises). But he is also very clear and has a more "lively" writing style, from what I recall. In any case, you can't go wrong with either.
Other books that deserve mention are: (1) Leary & Kristiansen's A Friendly Introduction to Mathematical Logic, which, as the title says, is very friendly and has a similar coverage to Enderton; (2) Boolos, Jeffrey & Burgess's Computability and Logic, which has some really nice chapters on models of Peano Arithmetic (including topics not often seen in this level, such as Tennenbaum's theorem, which states that the only recursive model of PA is the standard model); (3) Dirk van Dalen's Logic and Structure is pretty okay (I didn't find it too exciting, but it is reasonably clear), but it is also the only general book that I know, at this level, which has a good introduction to intuitionism and proof theory; (4) Hinman's Fundamentals of Mathematical Logic, which is a little bit friendlier (but just a bit) than Shoenfield, but covers much more (e.g. the chapter on set theory covers not only forcing, but also has sections on large cardinals and the axiom of determinacy, whereas the chapter on model theory proves Morley's Theorem, which states that if a theory is categorical in some uncountable power, then it is categorical in all uncountable powers).
So those are my recommendations. Hodel or Enderton for a first contact, or, if you prefer something friendlier, perhaps Leary & Kristiansen. If you are really interested in models of PA, definitely check out the third part of Boolos, Jeffrey & Burgess. If you are interested in the rudiments of intuitionism and proog theory, check out van Dalen (though do note that he does not get to what I personally think are the juicy bits, such as Gentzen's proof of the consistency of PA). If you are in for a very rough but advanced ride, Hinman. Finally, if after you finish one of the basic books, you want some introduction to more specialized topics (model theory, set theory, etc.), I would recommend reading a specialized book, instead of a general introduction (as the aforementioned books by Kirby or Kunen).
