How to generate a controlled frequency sine wave using a microcontroller like PIC18F4550?
You can use an external DAC IC and have the PIC talk to it using SPI, I2C, or some other interface.  As you mentioned, you would use a lookup table in the firmware.  To change the frequency, just change the rate at which you update the DAC with a new sample from the lookup table.  Alternatively, you could keep the update rate the same, but skip entries in the lookup table to change the frequency.

If you need > 10V pkpk amplitude, tied the DAC reference to +12V if you are using a unipolar DAC. Or you can use a bipolar DAC and tie Vref+ to +5V and tie Vref- to -5V, which should give you close to 10V pkpk.