I recently purchased a 128x64 bit graphical LCD from Adafruit, and decided to avoid using up most of the free ports on the Arduino, by connecting it via I2C, using a MCP23017 16-bit I/O expander chip.
This is a photo of the results:
Note that only four wires go from the LCD screen to the Arduino.
The cost is pretty minor - the expander chip sells for around $US 1.20 to $US 2.
More details, how to wire it up, and library code is available here:
The library has fairly basic features, however you can draw text, clear rectangles to black or white, draw boxes, and "blit" in predefined images.
The nice thing about using I2C is that almost all of your pinouts on the Arduino are still free for connecting up to whatever it is you want to show on the LCD screen. And indeed since I2C can be shared, you could also use the I2C for some other device as well.
I'm no expert on making circuit boards, but it seems to me that this would be a useful project for a "backpack" board. It would basically only need the expander chip, a row of 20 holes for connecting to the LCD, and the contrast pot on it somewhere. I used a couple of resistors to pull the reset lines high, but they could probably just be straight wires. Any advice on how to go about getting such a board made would be welcome.