I'd like to recommend "Startide Rising" and "The Uplift War", by David Brin. Aside from being very enjoyable books, they're a big source of new ideas -- these books singlehandedly made me appreciate the goals of the Internet Archive.

Also, I've never understood the popularity of "Stranger in a Strange Land". I've always been a big Heinlein fan, but Stranger in a Strange Land always struck me as a book that was important and shocking and ground-breaking once upon a time.