As these guys have said, whilst you can still get 'CPLDs', many companies have blurred the lines between these and FPGA's, effectively creating convenient FPGA's, with on-board config memory, oscillators, flash etc.. A good example is the Lattice XO2/3 series.
I got 'in' to CPLD's about 16 years ago, back when there were plenty of 32/64/128 macrocell devices in PLCC packages - I still have quite a few MAX7000's (Altera), 9500's (Xilinx), and lattice MACH4A's. Whilst I could probably still use them in some projects, the hassle of finding the older software that supports these, and possible issues getting them to run on windows 7/10 means they just collect dust - and thats a pity. But I'm going to order a XO3 board, which for £20 has more than enough gates for anything I'll need - its almost shocking how powerful/large these devices are on boards that cost far less than the older CPLD boards (that had 32 MC's..). No doubt I'll end up like these guys who use CortexM4's to make a few LED's flash.
Back to your needs. The biggest restriction is of course, 5v logic. Yes, the 9500XL from xilinx (I *think* that is still supported) has 5V tolerant IO's, but adding HCT buffer chips to its outputs to get 'true 5v' sort of defeats the point of using a CPLD to replace said 7400. And even though much newer devices can have 3.3V IO (with a separate core voltage much lower) I don't think any are 5v-tolerant, and perhaps, even though you get *much* more logic for the price, using a modern FPGA would be overkill, and for knocking up 'old' computer hardware - it could all be done in the FPGA anyway, which again, maybe defeats the point of building old computer hardware..
If this is just for one off's, and you feel you really need a 5V device, I can supply you with a list of chips I have (in the UK here), and try and find the older versions of Altera/Xiliinx/Lattice software that will allow you to configure them. (Pretty sure Altera and Xilinx have ftp servers providing very old versions of their software). Simpler devices such as these also have the advantage that they have a lot less 'options' (IO slew rate, thresholds etc..) that would have to be configured for a modern device. So yes, cost is generally proportional to the age of the device.
You could try one of these:
http://www.ebay.co.uk/itm/XILINX-XC9572XL-Development-Board-CPLD-Logikgatter-/181974808918?hash=item2a5e8b3956:g:2UQAAOSwCQNWgVfGBut actually programming them can be an arse. Whilst Altera has the Byteblaster - and the many cheap clones around, xilinx programmers tend to be more expensive, unless you have a parallel port on an old PC then you can knock one up pretty quickly. It really is the software/programmer rather than the devices features itself that make the difference.