Although I did not use the sparkfun protoshield (too expensive, as mentioned), I have bought and used ladyada's, the one from nkcelectronics and the one from nuelectronics. I also made my own, on standard protoboard, plugable into Seeeduino (with the awkward spacing between D7 and D8 resolved).
One of the most important criterion for me was the price. I would go after the PCB only, rather than the kit (with the few, very easy to find, components). The boards themselves are almost similarly priced, at around US$5-6, so they all score similarly here.
Another inportant criterion was the form factor. There are 2 standard sizes, it seems: one full size (as large as the Arduino board), the other one smaller (leaves the USB connector of the Arduino base board exposed, to avoid short circuits, I suppose).
Ladyada's is the only one (out of the 3) full size. The problem with the underneath USB connector (potential shorting by the metallic socket) is solved with an SMD area (no holes above the USB connector). Smaht :)
A third criterion was versatility, that is, how many components can be fit on the board, can there be SMDs, how much work (trace cutting, wiring/trace forming) one needs to do.
Although it provides ample room for TH components, the protoshield from nkcelectronics does not have and SMD area. I also had to do a lot of trace cutting (5 holes on each side of the middle rails are connected, a bit extreme for really small projects). The shield from nuelectronics had a nice SOIC 16 "footprint", where I could fit two 8 pin SOIC ICs (DS1307 RTC and 24LC256 eeprom). Trace cutting is minimal, since only 3 holes in a row (on each side of the middle rails) are connected. Ladyada's shield also fared well, but was kept behind by the 14 pin SOIC, which can hold just one 8 pin IC.
If stackability is important, you will find the shield from nuelectronics the cheapest to stack up, since it uses regular female headers. To stack the other two, one needs to buy the hard-to-find (or expensive) "stacking headers". These headers have longer (and more fragile, easily bendable) pins.
Personnaly, I prefer the protoshield from nuelectronics, since it met my requirements pretty closely. But then, for around same price ($5-6 a piece), I would rather design my own shield and have the PCBs manufactured by seeedstudio's propaganda service (for example), and replace the "blue collar" work (cutting traces, wiring) with "white collar" work (Eagle). This is what I am talking about.