I think you should definitely try a Kindle. Amazon has a 30-day return policy on 'em and nothing beats actually having one in your hand and seeing if you like the way it works. You can also get the first chapter of any book they sell as a free sample.
That said, I’m kinda like you in preferring dead trees when it comes to books. e-Ink certainly reads like a real book (it’s an unbelievable contrast to regular LCD screens if you’ve never experienced one), but real books have other advantages.
From experience, here are some negatives:
First off, reading on the Kindle isn’t really cheaper. You can’t check out books from libraries with the Kindle (though you can with some other e-readers). You can’t buy used books with the Kindle. You can’t sell your books after you read 'em.
You also have to take care of a $300 (K2)-$490 (KDX) device instead of a $20 book. You can’t just toss it in a backpack unprotected. You can’t nonchalantly lend it to a friend. You can’t leave it on the table at the cafe when you use the bathroom or put it over your head when you take a nap in your hammock. Etc.
Also, in regards to the Kindles in particular, they have horrible user interfaces. There is no folder support (making it impossible to organize your books/documents). PDFs are barely supported on the Kindle 2 (they require conversion and don’t always end up well); the Kindle DX supports them natively, but the screen is still too small for 8.5"x11" reading and PDFs take half a century to load and half a decade to page.
That said, if your main intent is to read plain-text novels (whether from the Amazon store or sites like Gutenberg), the Kindles do that really well. The Kindle 2 and Kindle DX just came out this year, so it’ll probably be a while before Amazon releases anything new. I’d recommend Amazon over any other company (except maybe Barnes & Noble, see below) only because of the cachet they have with publishers and authors (which directly translates into the number of books available to buy).
If you don’t mind waiting and you want a bigger screen, B&N is set to release their own e-reader with a true 8.5"x11" screen and double the catalog size of the Kindle Store, but there is no release date or price set yet. Otherwise, I’d go ahead and give the Kindle a whirl.
ETA: FYI, I’ve owned both a Kindle 1 and a Kindle DX, but eventually resorted back to paper books because they were cheaper and because most of the books I was interested in, including textbooks, still weren’t available.