First of all, you should have in mind that Linux is just a kernel, and what you are probably more interested in are all the userland programs that comprise your typical Linux distribution. I think it is best to start with a general Unix introductory text, because the fundamental principles have not changed in 25 years, and it is much better to understand the core Unix system utilities and how they plug together to accomplish complex tasks, rather than waste time with all the modern Windows-like interfaces that are fashionable in Linux distributions today.

There is one "classic" Unix introduction book that I can strongly recommend, and that you can probably buy used for a dollar: Exploring the Unix System by Stephen Kochan and Patrick Wood. Make sure to get the paperback edition that is about 400 pages. Also, apparently the authors are going to release an updated version of that book -- check http://www.kochan-wood.com for updates.

Once you learn the fundamentals of Unix systems, then you would be ready to learn the modern tools available in Linux distributions. Remember that is much more important to learn the principles and philosophy that Unix was built upon, rather than attempting to memorize arcane details.