I go for the DE0 Nano more than my other boards. It has a lot of GPIOs and it's spartan enough so you don't get distracted with other things. Also the speed rating is 6 so it's faster than other boards. And the size is just perfect, I also like that I can use old IDE ribbon cables.
You can buy generic accessory boards, use a few jumper cables and have a blast learning. Well at least I do find it fun.
http://www.wvshare.com/column/Accessory_Boards.htmAs for complicated, the DE0-nano has that myfirst fpga sample that should help any uninitiated to start learning in a well organized step by step tutorial. I don't care much for the avalon interface or soft cores I want to learn to drive them myself from the datasheets.
If I wanted an mcu then I'll get the $200 DE1-SoC Board with an embedded dual-core Cortex-A9. The FPGA in it goes for over $200 in Qty 100.
If you want cheap, the BeMicro CV goes for $35 at Verical (found it via octopart). Although not starter friendly since it lacks samples and even their hardware guide doesn't include the MicroSD pins, luckily the schematic and an older version of the guide includes them. It couples with Analog devices dev boards via a $50 adapter (too expensive) also you can hook it to the BeUSB 3.0 that uses the Cypress FX3.0 usb hub chip and verical has it for $72 (normally $99).
As for CPLDs Altera's Max V are really FPGAs in disguise, on their newly announced Max X series they are actually categorizing them as full fledged non-volatile FPGAs.
On top of that Intel's announcement of Xeon with FPGAs built in (probably Alteras since Intel let them use their 14nm trigate tech) makes it more interesting. As a programmer it would give me an edge if they catch on beyond the data centers.