If you are just learning HDL and FPGA's, I suggest the major factor in your first board is the available educational material.
I personally learned with the Basys 2 and this free course by Hamster. It is written for the Basys 2 and Nexys 2 board (both Spartan 3E boards). The course goes through the all aspects of those boards, from the leds to the on board ram, to VGA output. The course uses VHDL which I suggest learning but of course this is my bias as I have not used Verilog (Verilog seems lower class to me and is the vibe I get from any FPGA tutorials, articles, etc).
Keep in mind, that the course can be used with any board that uses Xilinx, but you will need to figure out your own constraints file. The constraints file connects your VHDL to your board peripherals.
I have since bought a more expensive and better board (Atlys Spartan 6) but I haven't used it much and I just seem to use my Basys 2 for everything so don't worry about buying something at the Spartan 3E level.
The second factor is the available toolchain. I have only used Xilinx and Digilent boards but they seem great and you can get Xilinx WebPack which is completely free. I have not used Altera stuff at all but my bias is Xilinx.
Another factor, is the peripherals and IO available on the board. This includes: switches, buttons, LEDs, IO, VGA, ethernet, etc. This allows you to experiment with all sorts of projects without having to get external parts set up right.