When I was looking for programmable logic, I jumped into CPLDs because they seemed straightforward and had a low cost of entry. I bought the Atmel ATF15XX development kit, which cost $100US, but really all you need is a chip, which comes in PLCC and TQFP packages so you'd need an adapter to prototype with it, and a dongle, which you can build yourself. It is a FLASH based device programmed through a JTAG interface, in-system programmable. Basic software is free. You can fit a whole lot of combinational and sequential logic into one of these babies.
j.