So, I spent a bit of time addressing this problem.
Thank for the comments! First, I did notice that certain frequencies are more problematic than others. Higher frequencies tend to have stronger harmonics which fold over. However, if you have a tone that divides evenly into (sampling_rate/2), the folded harmonics land on top of the non-folded ones, so it sounds ok. Still, it's not right, but it sounds ok. I also know that I could process things at a higher sampling rate internally, and post filter it.
What was bothering me was this - in the "synthesis" problem, I know _everything_ about the waveform I'm trying to generate. So, it seems that using that information from N previous samples, I should be able to come up with a "optimal" solution in some sense.
As it turns out, one approach is to apply a window filter to the previous bit or bits, before generating the samples. The simplest thing is to use a one-bit-long rectangular filter. This is easy - and definitely sounds better than doing nothing. But it doesn't do a very good job as a low pass filter. For one thing, the cutoff frequency is fs, not fs/2 - but it does roll off well before that. Some of the other modules in the discrete sound system do this already as well.
Finally, I experimented a bit using a low-pass filter based on a Kaiser window. This gives great results, but you really need to use at least a few more of the previous sample bits to get decent results. 10 or so is darned near perfect.
Anyways, I'll probably look at some other approaches, including optimal low-pass filter designs, but in the end I'm not sure it's worth doing much more than a rectangular window.
A fine excuse to learn more signal processing, anyways!