Haven't looked at using CPLDs for quite a while but when I've used them they've been a lot cheaper than FPGAs.
I would forget 5V tolerent parts, 5V is old school, translate down to 3V3. Xilinx 9500 series although 5V tolerent are more or less obsolete now and they run hot. If you need 5V tolerent then go for the 95xx series whilst they're still available.
Xilinx CoolRunner, based on a Phillips design, runs at 3V3 or less and is a good solution if you want low power. Some of the Altera MACH cplds don't have true CMOS output stages, they're totum pole so useless if you need a symmetrical output drive, read the data sheet. Can't comment on Lattice but they might fill the gap where Altera and Xilinx are probably less focussed on CPLDs these days.