What's the best starter's board?

I would suggest you get a board with easily accessible I/O ports, something like the DE0 with the Cyclone III. The reason for this is that you will want to control external devices with this (LEDs, motors, displays...) and most of the other demo boards have specialized connectors (mainly Samtec) that are not too easily accessible using wire-wrap.

The Cyclone III should be adequate for most FPGA learning until you start getting into high speed transceivers, DDR, ... Then you will need to upgrade to a bigger/better part.

... this is at least how I started. :-)