One of the most popular items on Sparkfun is 128x128 Nokia Color LCD screen. The protocol has been reverse engineered by various people and libraries made for Arduino and other platforms.
In general, if the screen has only a few pins, it's likely to have a built-in LCD controller and use SPI or I2C for the protocol. Such protocols are usually not very hard to RE if you have the original hardware it worked with.
On the other hand, if it exposes some tens of pins like for example the PSP LCD, it usually requires a dedicated external controller and might even use LVDS or other complicated signaling. Such screens are not a good choice for small microcontrollers.
A lot of LCDs are available on eBay, see for example this store.
Without more details it's impossible to give a specific answer, so here's some general stuff:
If you are wanting to display colour video (e.g. ~24 frames or more per second) then you will need a little more processing power than most 8-bit uCs can provide.
To give an example, say you have a small 240 x 320 colour TFT display with up to 18-bit colour. 18-bit colour gives 2^18 = 262144 possible colours.
You will need at least one screens worth of RAM for the display memory.
To display one full screen will take 240 x 320 x 18 = 1382400 bits (1.38Mbit or 172.8KByte) of RAM.
If you have a frame rate of say, 25 frames per second then you have a data throughput of 1.38Mbit x 25 = 34.56Mbit or 4.32MB per second.
Of course you don't have to use the full 18-bits of colour info, so you can get down to e.g. 240 x 320 x 8 = 614400 bits per frame with 256 colours (~15.3 Mbit for 25 fps)
For black and white you only need 1 bit per pixel, so then you get 240 x 320 x 1 = 76800 bits or 9.6KB per frame. Throughput at 25 fps would be 240 x 320 x 25 = 240KB per second.
So unless you only want static (or slowly changing) images, I would advise looking at a 32-bit uC like a PIC32, or an ARM of some sort. The display controller ICs that drive the displays (i.e the thing your uC talks to) usually have at least a frames worth of memory, sometimes more, so you can work with limited RAM if you shuffle things about a bit but generally the idea is you make your changes in uC RAM then update the whole screen at once at your specified frame rate.
Microchip have a few TFT dev boards and a Graphics stack to help with development, although I wouldn't go for anything less than the higher end PIC32s for driving them.
Depending on your resolution/colour/sound requirements, a more capable ARM might be better, they range from speeds of 40MHz up to GHz, so plenty of choice - the development options are generally not quite as budget friendly though.
One excellent chip is the STM32F4, check out the STM32F4 Discovery board, it has everything you need to start using it for £10 (yes, really) For this you get a 168MHz uC with 1MB Flash, 192KB of RAM and more peripherals than you can shake a stick at. Plus on the board there is a MEMS accelerometer and microphone, codec and headphone socket and STLINK2 programmer (can be used to program other ST chips) included.
On the down side, the development is not as friendly as e.g. Microchip or Atmel - they don't provide an IDE and the documentation leaves quite a lot to be desired.
Random video of STM32F1 playing QVGA
Best Answer
Parts selection is actually quite a lot of work. Especially to vague requirements. Even just the question of an LCD screen is complicated (what size? pixel addressable? integrated controller? e.g. Efficient display of simple text/graphics on color LCD by ARM )
Then there's the question of what architecture(s) your operating system should run on, what features it should have, etc.
The video appears to refer to some sort of generic PC operating system, designed to boot on the "bare metal" of a PC. For that you will be best off with an old or cheap laptop to start with.
If you want to build your own OS, ARM is probably a good platform to start with; you might be able to find a dev board with a built in LCD, that would save you a lot of hardware work.