The ATmega1284 is a good choice for uLisp: it provides a generous 128 Kbytes of flash memory, 4 Kbytes of EEPROM, and 16 Kbytes RAM, twice as much RAM as the ATmega2560, and is nearly half the price.
Although there isn't currently an official Arduino board based on it, it's available in a DIP package and so it's relatively easy to build a uLisp computer on a prototyping board.
As of Version 3.6 uLisp includes an AVR assembler that allows you to generate machine-code functions, integrated with Lisp, written in AVR code. The assembler itself is written in Lisp to make it easy to extend it or add new instructions.
You can create a complete circuit on a prototyping board, using an FTDI USB-to-serial converter to program the ATmega1284P via the serial port, and use the Serial Monitor for uploading uLisp programs. There are several alternatives available; I used the FTDI Basic Breakout from Sparkfun , available from HobbyTronics in the UK :
Connecting an FTDI USB-to-serial converter board to an ATmega1284 for serial programming.
It includes an LED connected to pin 19 of the ATmega1284. For more information about building this circuit see Using the ATmega1284 with the Arduino IDE on Technoblogy.