I would highly recommend going with a CPLD board first (something like this), or an Actel flash-based Igloo Nano, or something small like that. Big FPGAs can be kind of overwhelming, and they have so many pins it's quite time-consuming to get things hooked up properly. Plus, as soon as you want to integrate one into your design, you'll realize they come in very large packages, with dozens of power pins. Most of them require several voltages to operate at, not to mention that most FPGAs are SRAM-based, and not flash-based, so as soon as you disconnect power, they lose their design. So, you have to at least have an Active Serial Flash Memory chip wired up, but many people use sidecar CPLDs or microcontrollers to load designs onto the FPGA.
It's all very overwhelming. CPLDs, on the other hand, are great! They're usually single-supply operation, and if you want 5V-compliancy, you can still buy older Altera MAX 7000 chips. Plus they have on-board flash memory, so they don't need other components to bootstrap them. And CPLDs function more or less the same as FPGAs, so you program them by writing VHDL/Verilog, or using a schematic editor. Same jazz about clocking (remember to use crystal OSCILLATORS not crystals!), and same manner of programming over JTAG. CPLDs have far less logic elements than FPGAs, so you can't toss soft processors on them or do anything too crazy. But if you're just getting going, they're definitely the way to go -- and they cost a couple bucks each and come in big-enough packages that can be hand-soldered, which makes them practical to integrate into little projects you may have on your desk.
Another option is the low-end Flash-based FPGAs made by Actel. I've been recently playing around with the Igloo Nano Starter Kit, which is about $100. These devices are just big enough to fit an 8051 core on it along with some custom digital logic, so they're a great option when you're mixing program-flow states with custom logic.