Apart of having all the messages in PCM files there is also possibility to use TTS (text to speech) There are small and compact TTS engines out there suitable for Arduino port. Here two I am using (with AVR32):
Tiny Speech Synth by stan 1901
just port it to your arduino (removing the waveout stuff and just use the buffer as PCM). The only lib it really needs is math.h
for sin,cos
. It may need a bit more work to actually make it more comprehensible but its not that bad when tuned the frequencies ... its using floats
heavily but I think port to integer math is also possible ...
KECAL 1.0 ports for ATMEGA
its much older TTS engine originaly from ZX Spectrum but its a bit less comprehensible especially with low quality reproductors (like buzzer) ... But id does not need PWM or DAC ...
I do not know of any more recent OpenSource TTS engine compact enough for MCU platform all I know of are too big or relaying on SAPI,.NET or other OS integrated stuff making them useless.
The #1 is simple and commented enough to make changes improving the phonemes. The #2 was heavily optimized for speed and size (it run on ~4MHz Z80) so no way to improve quality there.
Btw there are also IC for TTS out there so that might be even better choice...
[edit1]
Take a look at this:
Among other things I added there very good quality and low CPU demand TTS engine ported from Z80 asm into C++, which can be directly used by MCUs ...