I recommend the Altera 'Nios II Development Kit, Stratix II Edition'. Big FPGA and one year Quartus & Nios License. Way more expensive than those cheap $150 boards, but still a bargain. The Santa Cruz connectors interface nicely with self-made circuits/breadboards, so no need for a prototyping area.

The 'Cyclone II FPGA Starter Development Kit' is my low-cost recommendation.

For Altera, go for StratixII or CycloneII. With Xilinx, choose Spartan3(E) or VirtexII/Virtex4. Those are the Families that are hip at the moment.

Verilog or VHDL is a location issue, in Europe you'll finde more VHDL and in the US more Verilog gurus and jobs. Both languages are more or less equal.

To start with you can get away with about $100, but easily spend more like $1000, depends on how serious you are on this matter. The more the merrier. Anyway, money is not really the issue, you'll need lots and lots of time learning and experimenting, especially if you're coming from the software world.

I recommend not to pursue anything 8051 on a FPGA.

Switching between vendors is not that hard once you're familiar with the whole FPGA concept of one vendor. But still its learning the tools and workflow one more time which might take a couple of days.

Not in your question but mentioned elsewhere, i recommend not to start with CPLDs. They don't feel any different in a proper HDL design and you grow out of them too soon.

The question is, what do you expect?

Cheers, Roger