A larger PIC would fit your needs, for instance
PIC18F4685 has 96K FLASH and 1K data EEPROM,
PIC18F2682 has 80K FLASH and 1K data EEPROM,
PIC18F2585 has 48K FLASH and 1K data EEPROM.
You shoud take into account the speed you need, how large is the rest of the application, beside the LUT, the number of I/Os, price, etc
Atmel also has a few large 8-bit microcontrollers, from the ATMega series.
A LUT is a Look Up Table. Typically this is a hex image that gets uploaded into FLASH. Essentially you want a microcontroller that has a large FLASH ROM and the ability to read this FLASH from executing code. Atmel AVR parts can do this, PICs may also have this feature, I do not currently use them.
The stored data is easiest placed into EEPROM, which was already mentioned.
For reprogramming, Atmel AVR has the ability to use a bootloader. This small program allows you to reprogram via a serial port. Their parts also support ISP programming and JTAG programming. Again, PICs may have the same features.
AVR microcontrollers can be programmed using simple ISP, bootloader or JTAG(mega series). These doesn't require additional circuits in the board except connectors. I Believe other brand microcontrollers may work well. I would say, it also depends on what performance do you wan to achieve. and what design it is going to be. Any special peripherals power down modes etc...