As many have stated, both Xilinx are Altera can be good routes. Note that while they Altera tools support Linux, their freebie Web edition does not, and the full kit is more than you'd want to spend. Any Xilinx starter kit should be fine for tooling around. I'm not sure your experience level, so I'll go with the basics...
I'm a young n00b in the FPGA world (two years design experience out of college now), so my experiences are pretty recent. I've got an EE degree, and would say first of all, get a firm grasp of logic design. Do you know what a flip flop actually is? Are you familiar with things like setup and hold time? If not, start out with a lot of reading. Horowitz and Hill's "The Art of Electronics" is a good standard...there's a lot of analog stuff that's "less relevant" to you, but there's a good section on digital design that's a great start.
One of my young programmer colleagues was looking over some of my code, and seemed to think it was pretty easy...the syntax seemed pretty straightforward, he liked the idea of combinatorial logic being so easy to implement, etc. He started tinkering himself, and VERY quickly realized that it was much more complex than he thought when issues of timing were thrown in. A fundamental knowledge of how signals are propagating through the device is key. It's not just PROGRAMMING, you're programming the actual hardware (or making fancy lookup tables, whatever. Get off my back!).
As designs get more complicated, you'll need to learn how to use some tools to analyze timings. Altera has Timequest, not sure what Xilinx uses. In college, I managed to get away with the bare minimum of analysis, but I consider this to be a flaw in my education...to do things right, you should do proper timing analysis.
I have an Altera starter kit I dink around with myself when I'm not at work, and it's definitely worth the time to learn the basics if you're an eternal tinkerer. Finally, the best advice I can give you...don't forget to use VIM as your editor, or you're just setting yourself up for failure.
