Hi
1) Select a display which is supported by an existing library. Study the Arduino Playground. There is a list of libs for graphics displays. You might also look here:
http://code.google.com/p/u8glib/wiki/device. At least choose a display with a controller which is listed on the u8glib page or the Playground page.
2) Choose parallel mode displays only if you have enough available pins, otherwise use SPI. Avoid I2C, it seems to be slow and is not supported so well.
3) Better choose monochrom displays. I personally think, that the Arduino Uno has too less power to driver TFTs. For the same reason carefully select the display resolution. Anything above 200x200 probably will be too slow.
4) On ebay you may find very cheap displays, but you will not get much support. Good support is provided for displays from
http://www.newhavendisplay.com or
http://www.lcd-module.com/. Also displays from dfrobot, adafruit or sparkfun are good and reliable choices.
5) Level shifting: To my knowledge two controller do not require logic level translation: KS0108 and ST7920 based graphics displays. Most other displays require an additional level shifting circuit (e.g. 74HC4050)
Hope this helps,
Oliver