Before you get in to FPGAs, you should understand what's ahead for you. Designing with programmable logic is conceptually very different from microcontrollers. As such, there is a steep learning curve involved. To start, you might have seek out an overview of some basic hardware building blocks (NOT, AND, OR, XOR, flip-flops). When you design with programmable logic, you don't always have to be thinking about each individual logic gate that will be used, but there are many traps for those who don't have an understanding of the hardware underlying the design. This leads me to hardware description languages. You will need to look into either of two HDLs: Verilog or VHDL. Search the forums, there certainly already exists threads discussing the advantages and disadvantages of both. These languages picky and a bit awkward and don't work as you would expect if you are approaching it from say, C.
I strongly suggest that you look at one of either the two big companies that have been in the programmable logic game for a while: Xilinx or Altera. I would recommend either the
DE0 Dev Board which uses the Altera Cyclone III 3C16 for the
Digilent Nexys 2 which uses the Xilinx Spartan-3. I haven't personally used Altera, but most everyone I hear swears by their development software, but again, you can probably find another thread that discusses the difference. Each of these dev boards have lots of peripherals already installed so you don't need to wire something on a breadboard. This is especially valuable for learning with FPGAs because you can invest more time into understanding design concepts rather than worrying about wiring components correctly (though both boards have expansion headers if you want to eventually use them. At first you will have to suffer through boring basic dummy circuits that involve toggling LEDs with switches, but soon you will step up to more advanced and interesting designs.