<snip Yoda and Douglas' replies>
FPGAs are essentially a huge grid of flip-flops and combinatorial pieces called LUTs or lookup tables that offer a pre-programmed truth table. Overlayed on top is a hierarchical routing web that can be soft configured through the same programming. You can implement just about any circuit Depending on how the synthesis program takes your logic rules written in a high level description language (eg. Verilog or VHDL) and connects the LUTs and FFs, there may be routing and propagation delay. The tools generally accept preference on optimizing for route delay or gate area.
CPLDs have historically been small in terms of logic blocks (<100) but are instant-on thanks to on board flash. FPGAs have historically been larger in terms of logic blocks (thousands up to million), include specialized blocks such as embedded block ram (EBR) and serializers-deserializers (SERDES), but have to be programmed on power-up or auto-load from an off-board flash. However the lines are blurring constantly as both are converging rapidly and the terms are nearly interchangeable with respect to modern devices. Lattice's MachXO2 line and Xilinx Spartan 6 are good examples of what I would consider hybrid parts.
SPLDs (PALs) are much simpler devices and have been in wide-spread used since the 70's. There have been many incarnations but the current surviving type is the 'V' series. V's contain both combinatorial and registered logic (1x FF) per output pin and are instant-on thanks to an on-board EEPROM. Common types such as 16V8s and 22V10s can generally be used to replace any prior type of the same pin-out and many 74xx devices. For comparison a SPLD typically has 10 ('ish) logic blocks - one for every output. GAL is a commercial brand of PALs licensed by Lattice and offers little to no difference than a generic PAL.
To Douglas' point about incremental testing/debug... The routing matrix is very versatile. If you have an intermediate net you want to examine off-device, you can simply route that out to a second pad. Doing so may add some additional route delay, but it's negligible for this sort of application. I frequently include a header connected to some spare I/Os on FPGA designs so that I can route signals I'm particularly interested in debugging to a off-board logic analyzer.
Programming a variety of JTAG devices is a simple as buying a $35 DP Bus Blaster and using OpenOCD. Many PROM programmers will do SPLDs (16v8 & 22v10s at least) in DIP packages or SMT with adapters.
To yoda's point about soldering... YouTube is full of SMT soldering tutorials. I greatly prefer SMT to through hole. It's quicker to assemble and produces smaller cleaner more feature rich boards. And SMT parts are generally cheaper and more available and have a wide application domain. You don't need expensive tools however I must admit you will need some practice and patience. With a temp controlled iron and lots of gel flux, drag soldering is very forgiving. N8VEM is pretty clear on the through hole position though. The intent is to keep the home-brew project feasibility open to the largest possible audience. However if you are interested, please continue to investigate.
There are some really fun FPGA and CPLD eval boards that come with on-board programmers. Many have pinned headers that could be plugged down onto a through hole board if one wanted to interface them to a legacy system. Be careful about voltages however. Most modern devices are 3.3 volt I/O and are not 5V tolerant. The ones that are are generally older smaller CPLDs (<100 logic blocks). I've found the most turnkey interface to 5V systems is one of many FET based bus transceivers available from many suppliers.
Sorry to write a book, but I hope the information is useful at least.
-Alan