First, the headline news: the Nano pretty much blows the Arduino Stamp/Mini away, and I would expect it to replace the Stamp in the marketplace. In most prototyping applications, a Stamp by itself is not enough--you also need the USB board, and together they are about $10 more expensive and 30% larger than the Nano (which has USB built in). The Nano also has a physical reset button and automatic hardware reset when uploading new code, while on the Stamp you have to connect another wire to get that and there is no reset button. Here are all of the Nano's technical specs and features.

The Nano also has a number of advantages compared to the Boarduino, although it's more expensive. Aside from being about half the size, it has the aforementioned automatic reset when uploading code, while the Boarduino, which uses the FTDI cable instead, requires a manual reset [UPDATE: see comments for some clarification on this]. It's also got two more analog input pins, thanks the surface-mount ATMega168 chip having more pins than Boarduino's DIP version.

As it happens, we still prefer the Boarduino in a few cases (and not just because we use its parts to make our ArduPilot and BlimpDuino kits). For certain low-power applications, such as our BlimpDuino, you want to run the ATMega at a lower clock speed than the usual 16Mhz, so in those cases you'll want to make the crystal removable. (Typically we'll put the crystal in to program the chip, then remove it to run at the lower speed). That's not possible with either the Nano or the Stamp.

Here they are all together on a breadboard for size comparison (click for larger version):

Finally, a point about breadboardable Arduino boards vs. stand-alone dev boards like the Decimila and its mini "proto shield" breadboard. The Decimila is a nice and compact combination of an Arduino, power supply and breakout connectors for the pins, but the tiny breadboard that fits on the proto shield is too small but all but the simplest projects.

For most projects I prefer to use a breadboardable Arduino with a proper full-size dev breadboard (I use a Parallax professional development board, which has loads of useful features and goodies but is too expensive if you're not planning to use Basic Stamps, too). The one shown above, for instance, is being used to prototype RC mode for our blimp controller, which is way too many wires for the little Decimila breadboard. My advice is to get a full-sized breadboard and power supply and use the Arduino Nano. I think it's the best version of the Arduino currently available.