Cheapest solution is going to be the greeting card ICs, however i think those are maskrom so have to be manufacture with the sound (ie they are not programmed).
Easiest solution that's still cheap is using the cheapest micro you can find with the audio samples stored in flash along with the code.
Not sure if a PWM DAC will be fast enough, should be.
But a cheap audio amp made from discrete components is cheap as well