For the current book club, I've chosen something more lightweight with a more relaxed writing style. Although I'm slightly concerned about the level of rigour in this new book, I'll be able to assess it better as we make more progress through the book.
Rudin is also on my mind. But maybe that's for a future series of book club meetings!
In my opinion, Rudin is a great book if you're reading it under the guidance of a good teacher. For self-study, I don't know of any particular alternative to recommend, but I would select something more "talky" -- i.e. which goes more into the background, motivation, and philosophy of the subject.
In my case, I was a CS major, and I had experience with proof assistants, so it was doable with many excursions to Wikipedia, math overflow, ProofWiki, etc..