You can also get some Xilinx proto boards off of eBay. I checked the link that you provided, and they look interesting for the low end.
Assuming that you are not going to be building a 200MHz 1,000,000 gate monster, there is little reason to choose one manufacturer's lower-end FPGA over another manufacturer. Assuming that you want a few thousand gates just for playing with, here is what I would do:
1) Check out the major manufacturers (Actel, Atmel, Altera, Xilinx) and see what software they offer for free. While an individual FPGA could be $10 in quantity, the software might be $1000 or more. So let software drive you hardware purchases. This is the best approach for the hobbyist. On the other hand, if you are developing a poduct and hope to sell 10,000 of them, choose hardware first and let the software follow. Be sure that the software can go all the way from VHDL or Verilog in to a programming file out. Some vendors offer EDIF netist input for free, but charge for VHDL/Verilog.
I am also partial to Xilinx software because you can add "probes" which can bring ANY internal net out to a pin for debugging (without having to change your VHDL). I know that I have not seen this feature with Actel. I have not tried any of the other manufacturers personally.
2) Now that you have selected a vendor, go shopping for an eval board. New ones can be expensive, but eBay often had eval boards for older models -- which might be good enough for you.
3) You will also need a way to program this thing. Some parts (Actel ProAsic series) are flash-based, so you program that part directly. Most are RAM-based (including Xilinx stuff), so you need to program the programming EEPROM. So make sure that you have the right programming kit/cable.
Most programming is done throught an industry standard called JTAG. It is a standard at the pins, but NOT at the PC. This means that, even though the interface is the same, the cable will be different between manufacturers -- which is very annoying. In theory, Actel software could talk to a Xilinx cable, but this is not done because each vendor wants you to give them money for their own cable.
4) If you are doing complex designs, you might want to consider a logic analyzer. Here is one place for a PC-based option:
www.nci-usa.com. You can also get an old Agilent (formerly part of HP) for a couple of grand or so.
5) Have fun!