I assume you mean real embedded and not embedded linux or some other operating system thing.
All above are good, sparkfun.com is a GREAT resource for sub $50 cards. Dont buy the embed. The armmite pro is nice, trivial to bypass the high level canned package and load your own binaries (I have a web page on how to do it if interested).
Stellaris is good, the 811 is easy to brick so be careful, the 1968 eval board is not a bad one. The problem with the stellaris boards is almost all of their I/O is consuemed by on board peripherals. The good thing about the stellaris eval boards, based on what you are wanting to do is that all the I/O is consumed by on board peripherals. Lots of peripherals for you to learn how to write embedded code for.
You are going to eventually want a jtag wiggler, I recommend the amontec jtag-tiny, it will open the door to a number of the olimex boards from sparkfun. the sam7 and stm32 header boards are good ones as well.
the lillypad is a good starting place for arduino (sparkfun), same price as the arduino pro mini, but you dont have to do any soldering. get a lillypad and the little usb to serial thing that powers it and gives you serial access to program it. Just like the armmite pro I have a web page on how to erase the as-shipped flash and have a linux programmer that lets you load any binary you want not just ones limited to their sandbox.
avoid PIC and 8051 unless you are interested in a history lesson. the PIC32X, not sure my first one is in the mail, it is a MIPS 32 not a PIC core.
the ez430 msp430 board is a very good one, the msp430 has a very nice architecture, better than the avr.
You can get your feet wet in simulation as well. I have a thumb instruction set emulator, thumbulator.blogspot.com. Thumb is a subset of the arm instruction set and if you learn thumb then you can jump right into a stellaris board or stm32. My sim does not support thumb2, the thumb2 processors also support thumb, the transition to thumb2 from thumb is trivial.
avoid the stm32 primer boards, avoid the stm32 primer boards, avoid the mbed2 boards, avoid the mbed2 boards, avoid the lpcxpresso boards, avoid the lpcxpresso boards!!
I recently found a behavioral model of an arm in verilog that you can simulate your programs, have not played with it much. qemu-arm is probably easier, not a bad place to get your feet wet although it can be frustrating. Which is why I wrote my own.
ARMS own armulator is out there, in the gdb source release for example, easier than qemu-arm to use, but can be frustrating as well.
go to codesourcery for arm gcc tools. use mspgcc4.sf.net for msp430 tools. llvm is rapidly catching and passing gcc, if nothing else I expect it to replace gcc for the universal cross compiler tool. at the moment it is much more stable and portable than gcc when it comes to building for cross compiling (because it is always/only a cross compiler wherever you find or use it). the msp backend for llvm was an afternoon experiment for someone, sadly, I would really like to have that supported. If you use llvm, use clang not llvm-gcc.