I’ve recently been testing uLisp on an ATmega1284P. It’s an ideal platform as it provides 16 Kbytes of memory, giving about ten times as much workspace as an Arduino Uno. It is available in a PDIP package, so you can easily set one up on a prototyping board:
I used Sparkfun’s FTDI Basic board to provide the USB-to-Serial interface.