I wouldn't worry too much about what you choose, as there will be plenty to learn with even the simplest board.
I would definitely consider the other options apart from Altera/Xilinx, there is not really any "best" option as they all have different strengths. Same with the VHDL/Verilog - I picked Verilog based on a bit of research (here is one, no doubt controversial link I based my decision on) but mostly it was just the need to pick one of them, you can waste so much time (well I can) worrying about these things.

Saying that try and find one with good clear documentation, examples to follow and maybe a related forum or even a book based around it (e.g. Pong Chu's "Prototyping by Verilog Examples" based on the Digilent S3 board)
Digilent seem to be one of the best for producing good quality dev boards that are well supported.

An excellent way to learn is make your own dev board as Leon describes - I did a similar thing with an Actel (now Microsemi) ProASIC3 FPGA, and although it was certainly difficult with no prior knowledge I found it very rewarding and instructive, and the (simple) board worked fine in the end. Estimated cost was probably about $15 or so ($8 chip, $2 self-etched board for etching, $5 other stuff like oscillator made with hex inverter/crystal, LEDs etc)
It's probably just me but I usually try to avoid dev boards for learning purposes, rather as tools to use after you know the ins/out of the chips. Whatever works best for you is the key though, there are many ways to get to the same point.

Programming is commonly done via JTAG, and all the PLD vendors have their own programmers (you can try open source solutions but expect a rocky path) which attach to a header you place on the board.

I wouldn't worry too much about what you choose, as there will be plenty to learn with even the simplest board.
I would definitely consider the other options apart from Altera/Xilinx, there is not really any "best" option as they all have different strengths. Same with the VHDL/Verilog - I picked Verilog based on a bit of research (here is one, no doubt controversial link I based my decision on) but mostly it was just the need to pick one of them, you can waste so much time (well I can) worrying about these things.

Saying that try and find one with good clear documentation, examples to follow and maybe a related forum or even a book based around it (e.g. Pong Chu's "Prototyping by Verilog Examples" based on the Digilent S3 board)
Digilent seem to be one of the best for producing good quality dev boards that are well supported.

An excellent way to learn is make your own dev board as Leon describes - I did a similar thing with an Actel (now Microsemi) ProASIC3 FPGA, and although it was certainly difficult with no prior knowledge I found it very rewarding and instructive, and the (simple) board worked fine in the end. Estimated cost was probably about $15 or so ($8 chip, $2 self-etched board, $5 other stuff like oscillator made with hex inverter/crystal, LEDs etc)
It's probably just me but I usually try to avoid dev boards for learning purposes, rather as tools to use after you know the ins/out of the chips. Whatever works best for you is the key though, there are many ways to get to the same point.

Programming is commonly done via JTAG, and all the PLD vendors have their own programmers (you can try open source solutions but expect a rocky path) which attach to a header you place on the board.