I also highly recommend Papilio. I recently got a Papilio One with 250K gate Spartan 3E and FTDI USB chip for JTAG programming and serial access. At US$38 it's the cheapest USA board I know of with a large FPGA. DUO will give you a lot more capacity, performance, and RAM.
Update: I backed it. The Early Bird boards are going fast -- fewer than half left. Project just passed 30% funding. I've done a lot of work with Xilinx Spartan-II, Spartan-IIE, Spartan 3A, and Spartan 3E. Should be interesting to check out Spartan 6 when the boards come out of the oven :-)
The Wing interface on the Papilio boards is pretty easy to use. I've designed a couple wings myself.
I've got one that has spots for GPS, IMU and RTC modules, as well as two Pmod ports. The Pmod is an interface layout used by a a number of development board companies. This one will be used with a Papilio on my tele-presence robot at some point. I can use it with any of my Papilios. Presumably, designing one for this new Papilio would be just as easy.
Darn. I missed the Zero day award. I did, however, make the Early Bird Special, and upgraded to 2MB of RAM, and the Classic Computing Shield. Jack's at 25% of his goal after just launching today. Very nice.
I already own an original Papilio and a Papilio Pro. This one sounds like a great addition to my set.
If you're interested in exploring the worl of FPGAs, I highly recommend one of Jack's Papilo boards.