I tend to design more in FPGA vs CPLD land, so I can't really give you a good recommendation for you there, other than to look closely to the Max V family (Up to 1700 macrocells or 2210 LE's)
The EP3C25 is in full production. And is currently available at Digikey. (Although that package is a non-stock at Arrow) The U256 is probably a much more popular package.. This may be overkill for your design however.
Right now it looks like you are in a 128 macrocells which is approximately equivalent to 208 LE's.
The EP3C25 is 25000 LE's or approximately 15000 macrocells.
The EP3C5 is 5136 LE's or approximately 3160 macrocells,
As far as longevity, they are still in production with Cyclone and Cyclone II devices, so I don't think that's an issue yet. My only concern would be to the package, since the BGA's seem to be more popular these days.
My suggestion is to get your logic design done if possible, then fit it to either Max 5 or Cyclone 3 families.
If you want to go Cyclone III, build the board so it's compatible with all family members in the package.. (Be careful here, some IO's in one device are VCC's/GND's and/or NC in other family members).
That way you can put the biggest family member on the board for the development, then shrink it down for production without changing the board.
Pete