Dear Rohan,
First let me say that I got a little jealous after reading your first paragraph! What you are about to do should be very rewarding and a lot of fun.
I think you are right to be concerned that many students will find Rudin's book [as an aside, I don't really like this "Baby X" stuff: it seems not so subtly discouraging to describe university-level texts in this way; you could say either Rudin's Principles or, if you must use an epithet, "Little Rudin", because it is indeed a smaller book than his other analysis texts] too terse in and of itself. Sufficiently strong students will consider it a rite of passage and adapt to it eventually, but the entire current generation of "off-Rudin" undergraduate analysis texts seems to be fairly convincing evidence that the average undergraduate needs somewhat more help. Which is not to say that Berkeley is populated by average undergraduates, but I think even very strong students, whether they realize it or not, could learn more efficiently if the text is supplemented. (It happens that this was the primary text used in the math class I took during my very first quarter at the University of Chicago. It wasn't completely impenetrable or anything like that -- much less so than some of the lectures later on in the course! -- but I think I would have benefited from some of the supplementation you describe. In any case I'm too old to give a really independent evaluation of that book now: I've had it for getting on 20 years and have read much of it backwards and forwards countless times.)
The good news is that the off-Rudin phenomenon is so widespread that there are almost infinitely many places to go for a source of more problems, examples and so on. You really can have your pick of the litter. But since you asked, here are two books I like a lot, one old and one rather new:
Gelbaum and Olmstead, Theorems and Counterexamples in Mathematics.
What it claims is what you get, and what you get is very valuable. Asking students for counterexamples is a great way to keep them alive and awake in such a course: it's so easy for a young student to get snowed under by the barrage of the theorems and not to appreciate that so many theorems in real analysis have somewhat complicated statements because the simpler statement you are hoping for at first is simply not true. Coming up with counterexamples really helps students participate in the development of the material: if you don't do any of this explicitly, the very best students will do some of it on their own, but for a lot of the students learning the theorems will amount to a lot of arduous memorization.
Körner, A Companion to Analysis....
This is a pretty fantastic book: a long, chatty text much of which fills in nooks and crannies and works very hard to get the student to appreciate why things are set up they way they are. For instance, by now a lot of instructors have realized the pedagogical need to provide more up-front motivation for the real numbers and the obviously important but initially mysterious least upper bound axiom. Körner's book carries this line of thought through more deftly and thoroughly than any other I have seen. He asks the question "What happens if we try to do calculus on the rational numbers?" and he comes back again and again to answer it. It's tempting to throw out an example of a continuous function on a closed interval which attains its maximum value only at an irrational point and just move on, but this leaves a lot of cognitive work to the students to really appreciate what's going on. Körner does much better than this. Moreover, Körner's book ends with the best list of analysis problems I have ever seen. There are literally hundreds of pages of problems, thoughtfully organized and appealingly presented. This is an invaluable resource for someone trying to flesh out an analysis course.
I see that I've now written at length and not addressed most of your questions, which concern the solution sets. That may be for the best: it's been a long time since I regularly wrote up solutions to problem sets. This takes me back to my undergraduate days as well, when they were handwritten and mimeographed: yes, that was a pretty strange thing to do even back in the 1990's. (I will advise you tex up the solutions rather than handwriting them, although even this is not as de rigueur as one might think: I have colleagues who think that handwritten solutions are more appealing. I think they're crazy, but oh well.) I didn't get any feedback on them and often wondered if they were actually being read. So I had better leave this for someone else to advise you.
Good luck!
If you're concerned about time, I don't think reading Calculus by Spivak is the best thing to do.
Either Zorich or Apostol is a great choice. I would say that they're "intermediate" in difficulty. Zorich contains more in-depth discussions of topics, and more examples than does Apostol.
If your goal is only to move on to Royden, you'll probably cover the material more quickly in Apostol. Zorich covers a number of topics not addressed in Apostol, such as vector analysis and submanifolds of $\mathbf{R}^n$. These are important topics, but not direct prerequisites for Royden. Still, I think with all the Lagrange multipliers and similar tools people use in economics, the submanifold topic is important if you want to understand the theory very clearly.
Zorich's first volume is quite concrete, whereas Apostol becomes abstract more quickly. This is probably because he doesn't want to duplicate what would be in a rigorous calculus book like his Calculus, although he does this more than Rudin's book does. His analysis book was for second- or third-year North American students, whereas Zorich's is, at the outset, for first-year Russian ones. Russian students have typically had some calculus in high school, but the practical portion of learning calculus continues into their first-year of university, with harder problems. So in Zorich I, you deal with hard problems on real numbers, rather than delving straight into metric spaces as you would in Apsotol's book.
Zorich covers only Riemann integration, whereas Apostol has chapters on Riemann-Stieltjes integration in one variable, Lebesgue integrals on the line, multiple Riemann integrals, and multiple Lebesgue integrals. The treatment of Lebesgue integration is less abstract than in more advanced books. Since it's limited to $\mathbf{R}$ or $\mathbf{R}^n$, it's more elementary, but at the same time there is some loss in clarity compared to the abstract theory on measure spaces. One reason to use Apostol might be a sort of introduction to the Lebesgue theory before returning to it at a higher level and "relearning" certain parts of it. Whether you'd want this is up to you.
The fact that both Rudin and Apostol have chapters on Riemann-Stieltjes, rather than Riemann, integration, indicates to me that they assumed students had already studied Riemann integrals rigorously, and would be ready for a generalized version right from the start. Considering the type of calculus courses most students take these days, this is rarely the case now. Zorich doesn't have this problem.
All in all, for a typical student who is good at math but didn't learn their calculus from a book like Spivak's or Apostol's Calculus, I think Zorich is the better choice because of the more concrete approach in the first volume (this doesn't necessarily mean easier). On the other hand, time constraints might cause you to prefer Apostol's analysis book.
EDIT: An important point that I neglected to mention is that Zorich's book will be much better than Apostol's if you aren't yet acquainted at all with multivariable calculus. A practical knowledge of some multivariable calculus is probably one of the tacit assumptions that Apostol and Rudin make about their readers, which is what allows them to deal with multivariable calculus in a briefer and more abstract way. Compare Apostol's 23-page chapter on multivariable differential calculus to Zorich's 132 (in the Russian version).
EDIT: Based on your later comments, I would suggest that reading
Spivak's Calculus,
Whichever you prefer of Apostol's Mathematical Analysis or Rudin's Principles of Mathematical Analysis.
would be a reasonable plan.
However, before beginning the multivariable calculus parts of those books, it would be best to learn some linear algebra and multivariable calculus from another source. This could be Volume 2 of Apostol's Calculus. You could instead skip straight to the multivariable part of Volume 1 of Zorich, but you'd have to learn the necessary linear algebra elsewhere first. I don't recommend Spivak's Calculus on Manifolds if you want to learn multivariable calculus for the first time. Also, you won't need Munkres - you'll get enough topology to start with in whichever other book you read.
EDIT: In answer to your additional question, these topics are mostly not discussed in Spivak.
However, Spivak is an excellent introduction to the mathematical way of thinking. That is, although you will not learn all the specific facts that arise in higher-level books (you do learn many, of course), you will learn to read and understand definitions, theorems and proofs the way mathematicians do, and to produce your own proofs. You will become intimately familiar with real numbers, sequences of real numbers, functions of a real variable and limits, so you will have examples in mind for the more general structures introduced in topology. You will also solve difficult problems.
So it is not that you will know topology already when you've read Spivak's book, it's mainly that it ought to be easier for you to learn because you will have improved your way of approaching mathematical questions. Countable sets are in fact discussed in the exercises to Spivak, however.
I can't guarantee that your trouble will "go away," but there is a good chance it will.
Also feel free to use Zorich rather than Rudin or Apostol, after Spivak, or even to jump straight to the multivariable part of Zorich at the end of Volume 1 and start reading from there.
Best Answer
I went to Berkeley and the real anaylsis class used Elementary Analysis: The Theory of Calculus by Ross. It is a bit simpler than Rudin but much more readable. We did pretty much everything.