Mod parent up +insightful.
I've been programming for over 25 years, most of that at the firmware/driver level in C. I went on a hardware quest (for my own edification) about a year ago, and I did an independent study course for credit at my local university. My focus was on Verilog (because that's what's used within my company), and it was truly a different beast than programming! I definitely had to train myself to think differently to accomplish that.
There are many good boards suggested by others in this thread. I used three boards myself. The first board I used was
http://www.xgamestation.com/view_product.php?id=40 - containing a Lattice Semiconductor CPLD. The board was a good starter because it was designed for education, and included a lab manual of quite a few projects. Potential downside: the lab manual and tools it comes with are not based on either Verilog or VHDL, but rather ABEL. I did everything in Verilog instead, and still used the lab manual as a source of exercises. The Mach64 board is fairly inexpensive.
I also used a board from
http://www.opalkelly.com/ -- this product is a little pricey as an educational device. Their hardware contains Xilinx parts. What I liked most about it though is its USB interface -- first, you can use their tool to download your hardware description without being required to flash the board (where many other boards require you to flash the image to exercise it). Second, and more interesting to me -- Opal Kelly's boards include virtual device libraries, letting you attach hardware to USB-carried channels for data I/O and triggering to a remote application. They include a library to allow you to write a remote application to support the other end of this. I don't know if they support Linux though -- everything I did on the PC end was under Windows.
Finally, a reasonably priced board is
http://www.embeddedarm.com/products/board-detail.php?product=TS-7300. This board is not centered around its FPGA, instead it's an ARM9 based CPU board. The board includes full embedded Linux support and all the typical devices you would expect to find, and it has a user-accessible Altera FPGA on board. Their linux distribution includes a tool to send a FPGA bitstream over to the device, letting you quickly test a new hardware description (like the Opal Kelly board, without programming flash). Potential downside here... the manufacturer includes a bitstream image that is used by default, which enables (among other things) its VGA port and a second Ethernet interface - and their open source Verilog for this device doesn't include those, so you sacrifice some of the board to define your own hardware. You don't sacrifice anything you can't use the board without though (there's another Ethernet port; there's a few serial ports, etc., which don't require the FPGA).
Good luck!