Intelligent LCD character modules are much easier to work with than virtually any other type of display.
Here's the one on my workbench computer, a 1x16:
There's a little more about it in the potpourri section, under "Displays". I have interfaced up to 4x40 with the computer for other projects.
You can also get intelligent character and graphics LCD modules with RS-232 interfaces built in. Go to any of the major distributors' websites and type "LCD module serial" in the search box. I'm sure the programming gets a little easier, but it requires another UART, like the 6551.
I also have a small graphics LCD that is interfaced by SPI, so I put it on the 65SIB. I have working sample code for it here. Here's a few seconds of demo video done for experiment purposes, using a random number generator to produce sets of 25 random segments then displaying the screen memory:
This one is 128x64 dots. These are reasonably priced in 240x128 dots as well.
LED displays like those made for calculators might be smaller, but will require more I/O bits to feed them, constant software attention for the strobing (which you would take care of with a timer generating evenly-spaced interrupts), will require more power, and if you use 7-segment displays, you will have to severely compromise many of the letters' and special characters' user-friendliness to get them in at all, even if you don't try to do both upper and lower case. Seven segments gives you 128 combinations, but many of them will be awfully cryptic! Here in my hand is a tiny 4-digit 7-segment (plus decimal points) LED display made for early calculators:
Maxim has serial-interfaced ICs with LED-strobing circuits to reduce the processor's overhead to feed these animals, sometimes with other functions built in, like a keyboard scanner. See this selector.
If you really need it small but want alphanumerics (which you don't really get with the 7-segment calculator displays above), another possibility (although expensive) is the Broadcom (previously Avago Technologies) HCMS-2963 and relatives. This one has four 5x7-dot-matrix characters that you can feed with any dot combination you want, and it fits in a 14-pin DIP socket and is X and Y stackable for more lines or characters. Mouser stocks them.
For one product, I used the National Semiconductor (now TI, unfortunately) MM5453, a 40-pin IC that's an LCD driver for 4½-digit 7-segment-plus-decimal-point watch-sized raw (non-intelligent) LCD. I drove it with the 6522's shift register output. It takes care of the strobing and prevents plating problems that could arise from a net DC current you might get if you were to try to strobe it yourself and didn't get it balanced. It does not form the characters itself, so you tell it exactly what segments to turn on, and you can make any characters the LCD segments allow.
The 6845 and 6545 (compatible) were popular CRT controller ICs in early PCs. The Commodore 128 used the 8563 for 80 columns.
A link to this small VGA interface from 4D Systems in Australia and available in the States from Microcontroller Pros was just posted on the forum. You would connect it to a 6551 or other UART, without the line drivers and receivers.  The Micro VGA apparently works similarly.
Obviously this is just the interface and requires adding a VGA monitor, but if you have the room for that and want it, this appears to make life easy. The other limitation I anticipate is that since it goes through the UART, it won't be suitable for fast graphics. You probably won't be playing movies on your 6502 creation anyway. :D
Geoff offers a small VT100-compatible ASCII video terminal board at
http://geoffg.net/terminal.html. It uses a serial interface to your
computer, and you plug a PS/2 keyboard and VGA monitor into it.
This page might be of interest too. If you want to take just his IC and built it into your board, see http://micromite.org/shop/add-on-gadgets/ascii-video-terminal-pic32mx250/.
Batsocks offers this postage-stamp-size 5V TTL serial to TV adapter at
and their 128KB SPI / 8-Bit parallel bus SRAM with PAL / NTSC composite video display controller IC.
The "Brad's projects" forum has a Generating Video Signals section. That forum does not get much traffic, but the section has lots of posts (all by ChuckT), and you're bound to find something good there. Daniel Tufvesson's page "Bitmapped video interface" using just TTL ICs and not being terribly complex was recently mentioned on the 6502.org forum. "Sagar GV" has a series of seven blog posts called "NTSC Demystified."
Here are some video topics on the 6502.org forum (and some of these have more links in them):