Scott Hanselman has blogged about what he thinks is the Six Essential Language Agnostic Programming Books. Can't say I can argue with any of the six he has choices, but let me make a few suggestions:
Patterns of Enterprise Application Architecture – Martin Fowler
My own personal opinion, may now be more important than the original Design Patterns.
Introduction to Functional Programming using Haskell
I actually have the original version of the book that uses a pseudo language instead of Haskell. Not entirely language agnostic since it is a book about functional programming, but required reading to understand in depth any of a number of the modern trends in the industry.
Algorithms in C++, Robert Sedgewick
Ok, the quintessential college text book still on most people's bookshelf. And we all know that even though it isn't language agnostic, we all us it in a agnostic way. Over the last twelve years, I have now used the book as a reference for developing in eight distinct languages (C, C++, Java, VB, C#, VB.NET, Ruby, Python) Looks like Sedgewick also has versions of the book for Java now.
On a random, but related note - a little bit of Andrew Conrad trivia. I did my graduate work at Seattle University in the same program attended by Steve McConnell (author of Code Complete, first book in Scott's list). In fact, during the last year we did a year long project which was sponsored by Steve McConnell and his company (Construx) where they acted as the customer and we were the development team. So I actually had a bunch of meetings with Steve where we argued app features and schedule.