We don't need anything close to say, 12 bit resolution, but I'm sure they will want more speeds than what's currently offered. Perosnally I think 10 speeds would be a nice compromise. As you say, I could do something similar to an R2R ladder but with relays and caps with 3 or 4 bit resolution.
That's a good way to save $30 in the board Orion was talking about earlier. The relays would have to stand the current consumption of the fan, and the caps must be safe for mains use. I think that's the way ceiling fan 5 speed controllers work. I took one apart recently, but it was all potted inside.