Now that Xilinx has released new chips, the old ones are pretty cheap. A Spartan-3A evaluation board is less than US $200. These have VGA, PS/2, RS-232, a character LCD, a rotary encoder, LEDs, switches, and a bunch of extra connectors. The main problems are that the DDR2 RAM is *difficult* to use without a proprietary core, and the FPGA doesn't have access to the USB link.
Digilent Inc sells Spartan-3E boards for less than US $100. These have an easier-to-use DRAM and provide access to the USB port (though I think the official driver is windows-only, there seem to be solutions for using it on Linux).
Xilinx's ISE runs natively on Linux (RHEL, last time I checked). With a little searching, it was easy to figure out how to get it to work on Ubuntu, including the USB JTAG interface on the eval boards.
I haven't found a great book for learning this stuff. Pedroni's _Circuit Design with VHDL_ is okay, but it's not particularly deep and doesn't cover the FPGA development process at all. I had to study the Xilinx tutorials to get things working.
Writing HDL code superficially seems like normal programming, but it's not. Think of it as a way to translate your already-completed design into a form the computer understands. If you don't do the up-front design, it will be hard to fix through refactoring. The simulators just aren't up to the task. Restrict yourself to a single edge of a single clock, and things will be much easier.