The free software dev stack is nearly non-existent with FPGAs because device manufacturers keep information about how to program their parts to themselves. That sucks for freedom, and on a purely practical level, I think it has held back innovation in the tooling and applications of FPGAs. They keep talking about "reconfigurable" computing, but their own tools make that vision an impossibility. There are free tools higher up the stack (e.g. Verilog simulators etc.), but eventually you need to deal with the device manufacturer's tool to generate the bit files.

The closest I've heard for a free stack is the reverse engineering effort going into "Project IceStorm". I am thinking about investigating that more. I think there has also been some limited reverse engineering performed on some older Xilinx parts. However, if you are just starting out, it is probably better to start with something like the Papilio. Anyway, I'd be interested to hear what you learn if you decide to do it.