I've been doing some more research into this myself. I'm still looking at different DACs, and starting to feel that a 16 bit one would be necessary to get the level of precision required by a volt/octave CV system. A CV Recorder is one of the projects I'm thinking about doing. If you're just tweaking a joystick, 256 values should be sufficient, but if you're trying to record precise note information, it's back to the 16 bit ADC/DAC combination. I think it would really require some external RAM as well. As far as stairstepping goes, you could always interpolate between output values, but that still means using a high-res DAC to get better precision.
What sample rate are you recording at?