I write FPGA code for a living, more in VHDL than Verilog, and more for Xilinx than Altera.
I would actually recommend that you don't buy a board at first. You can pick one out so you can decide on a vendor's chip, that's fine, but simulate everything, because that's what HDL design is all about. Both vendors offer a free version of their toolset and there's a free simulator with each of those. Or you can download ModelSim Starter edition. I wouldn't call either one Linux friendly.
As far as the board goes, I would recommend one of
Altera's Nios II Embedded Dev Kits. I feel that although Altera has a slightly steeper learning curve than Xilinx, they also have a nicer overall package than what Xilinx is currently offering. I'm speaking from the point of embedding a soft processor though, if that doesn't interest you, then either of the cheap Altera Cyclone or Xilinx Spartan kits will get the job done.
This is the only book you need on VHDL:
The Designer's Guide to VHDL by Peter Ashenden.
I haven't found a Verilog book of similar quality.
Buy several books on Verification and testbench writing. That's where the real work comes in, and it's significantly more work than whatever circuit design you're doing. Spend the time to learn how to write self-checking testbenches.
Read over the Synthesis guides for whatever vendor's board you choose. Understand how the constructs you use affect synthesis. There's a wealth of information in the Xilinx and Altera online documentation. There's also a lot of really of good snippets of code which are themselves useful but also typically contrast less and more effective constructs for synthesis.
And finally, I will echo the caution that HDL is not a programming language, it is a design language. If you do not have a fundamental grasp of circuits, logic design, and computer architecture, I would recommend you pursue those topics first.
