Linear Algebra - Strongly agree with the Strang recommendation; his book is a standard. Be sure to head over to ocw.mit.edu and check out the free videotaped lectures from his linear alg. classes (course 18.06). He is a terrific lecturer. There are also plenty of homework problem sets (w/solutions) and old exams (w/solutions). Stay away from "Matrix Theory" by Leon.
Analysis - Rudin is the classic, no doubt about it. You'll want to have it for reference no matter what. For a first introduction, though, many folks have better luck with Steven Lay's book or even Zakon. Zakon offers his book for download from his page at the University of Windsor. Lay and Zakon are different from Rudin in that they "bridge the gap" between the calculation-based based courses (Calc., DiffEq. LinAlg) to classes requiring proofs. I recommend downloading Zakon's book, taking a look, and if it feels too easy, go straight into Rudin or similar.
Finally, don't underestimate Schaums guides. They will never replace a good textbook, but having a stack of solved problems (albeit with occasional mistakes) to work through can be invaluable. They are cheap and I know that they have them for Linear Algebra and Advanced Calculus (as well as about every other subject under the sun!) They are also VERY useful when the GRE subject tests roll around and you need to review.
