Xilinx
I choose to use Xilinx as there development software is free (they even have a Linux version).
Also it possible to obtain there parts relatively easy and inexpensively, they even have a web-shop where you may buy there chips and you don't have to order 100 at a time.
Also the a schematic for the old version of there JTAG interface is available.
Software
I downloaded the free WebPack 7.1i package for Red Hat Enterprise 3 Linux I actually run Debian. The file was called WebPACK_71_fcfull_i.sh.
As root I ran the installer shell script.
I had to export DISPLAY=:0 before running the installer, please note that I did not write :0.0 as would be more common. This is a hint I found on a web-page last time I installed WebPack. The webpage I found last time may have been http://www.wolfteck.com/xilinx/native/.
Also I did't have to install extra libraries in order for the installer GUI to launch as I had done this the last time around. You on the other hand might have to, and this is a quit slow and boring process I might add. The sluggishness is caused by the fact that the installer script only returned one failing library at at time and even worse only after it had verifying the archive integrity and uncompressed it.
At the end of the installation ti kinda blew up something regarding it not being capable of running some script and finding some files.
Hopefully this won't affect its capability to program devices. Only time can tell this as I currently don't have a Xilinx part or a JTAG cable.

As my regular user I changed directory to where I had installed it and ran sh ./settings.sh after this I could run ./bin/lin/ise starting the main GUI. As I haven't added the path to my PATH variable I can't run it as ise just yet, besides I don't know if ise depends on the current directory for finding any files. At the moment I'm happy with this setup.Verilog
Language
I chose Verilog as the language I would learn. VHDL seems to be more powerful/high-level compared to Verilog. However Verilog appeared easier to learn and also more widely used than VHDL. There are even people saying that Verilog is superior to VHDL, as you get your work done faster in Verilog, but the debate seems semi religions in natur.

A Verilog quick reference