Hi there,
I have done a fair bit of work with FPGA's, they are pretty much my profession!
They are much much different to micro's, and may take a bit of getting used to. The basic building block of an FPGA is a slice. At a basic level this consists of a Look Up Table (LUT) with N inputs bits and M output bits (typically 1 or two). This can store any logical function you wish and is a combinatorial piece of logic, think of it like a tiny parallel EEPROM with 4 or 6 address lines and one or two data bits.
After this there is a flip flop, to synchronise this value to the systems clock. A large interconnection matrix then feeds this signal to another slice, and so forth. Trouble is this path the signal takes, must go through the next piece of combinational logic and be present on the flip flop (setup and hold) long enough before the next clock edge. So the bigger the design the harder this gets, as the signal paths get longer and longer. So although you design maybe behavourally correct (behavioural simulation proves this), it may not meet timing (you can do timing based, post place and route simulations too).
I would suggest downloading Xilinx ISE Webpack, Lattice's ISP Lever Starter (or diamond - I prefer ISPlever I must be honest), and go through some online tutorials using the simulator - before shelling out cash for boards.
If you are a student, the Digilent Atlys is a great buy (a lot of dev board for the money, it has a onboard programming via USB academic price of $200), but the cheapest way in to the FPGA world is probably the Lattice XP2 brevia but you will need a parallel port for the JTAG lead included (about $50, and comes with a parallel port JTAG lead)!
I started as a student with a home made parallel port programmer and a M4A5-64 home made board on vero. I would not recommend CPLD's (although easier) due to the limitations of such device. The brevia has approx 5000 LUT's and flip-flops whilst the M4A5-64 has 64 flip flops.