My first step, in my foray into embedded systems: interfaced a 4×20 character LCD panel to the Arduino. Details on interfacing any Hitachi HD44780 based LCD panel can be found here.
Went for the default parallel LCD’s. They’re cheap, about $15 for a 20×4 panel on eBay (HD44780). The serial ones cost about 2-3 more. These LCD panels allow you to use 4 data lines (with some bit-banging) instead of 8. Get one that is STN and transflective (vs reflective and transmissive), known for better contrast and brighter.
Check out also LCDProc.