Make:

If you search ebay for "serial lcd", you should get what you need. Even if you don't actually purchase them from there, it will still give you a few product numbers etc. to look up elsewhere.

Hm I really don't think you should bother with microcontroller.

Here you have link where Lirc, mpg123 and lcd proc are connected you can do lots of stuf only with these aplications. Just search for HD**** compiliant Lcd screen.

http://irmp3.sourceforge.net/news.php

But I don't know what is on the page because http://ofcourseitworks.com/content/view/9/2/ isn't working :(

Matrix Orbital LK202

LK202-24-USB
http://www.matrixorbital.com/product_info.php?pName=lk20224usb&cName=lcd-character-lcds

LK202-25 (serial interface)
http://www.matrixorbital.com/product_info.php?pName=lk20225&cName=lcd-character-lcds

I control mine directly from bash script

#!/bin/bash
stty 19200 raw -F /dev/ttyUSB0
echo -e "\xfe\x58$1\xfeG\x01\x02$2" > /dev/ttyUSB0

I know this isn't what you are looking for, but it gives you more capabilities.

Since the heart of this system is a computer, you could always get a vga to rca converter and get one of those little screens used for the PS & PS2. This will allow you to go a little further and display the next song or whatever.

Software: www.lcdproc.org it is a client-server model, so you can use it to display many things on one display.

Hardware: there are quite a few cheap parallel displays which can be driven from the parallel port. Both Matrix Orbital (listed above) and Crystal Fonz produce serial displays -- good quality, but sometimes out of some people's budgets. I like them both.

Another option these days is getting USB displays... just a couple bucks more than the serial one.

You could buy a used PalmVx or something like that with serial docking. With a little bit of hackery you can make it look good. There are some programs out there that allow you to

- display songnames
- get a console
- display nifty visualisation
- tap the screen for the next song

I bought a perfectly working IBM Workpad C3 (Palm Vx in black) for 20 euros at ebay.

I've got one of these displays, and it works rather nicely - runs straight off my serial port and a 5V supply:

http://www.pjrc.com/store/mp3_display.html

I picked mine up on eBay for about £20 from the owner of this site:

http://www.btinternet.com/~markd833/LCD/intro.htm

I have here, on this very desk, a 40x2 (maximum 40x4 due to the addressing) Hitachi HD44780-controlled LCD screen that runs through the parallel port and powered through USB (suboptimal solution, but it works). It's quite simple to build too (just soldering, really), the instructions can be found at, say, http://www.overclockers.com.au/~mwp/cc/guides/setup-hd44780.htm - just substitute the molex for an USB connector if you want to.
If parallel is an option, you can pick up such a screen from probably any given, er, Radio Shack, or just go and look through old gear from somewhere, most of the controllers seem to be HD44780 compatible or at least almost compatible. You can then run this device using say, LCDSmartie on Windows, or lcdproc on Linux.

Oh, I remember those heady days before the iPod! I wrote my own mp3 jukebox system in Python (with help from an O'Reilly Python book, btw) back in 2000 called "MPy3" which utilized a CrystalFontz (http://crystalfontz.com) LCD. It was a simple serial-port interface (only a little soldering!) and I found that they had an excellent control interface that was simple. So simple that despite my relatively little experience w/ Python at that point, I managed to write a program to control the LCD in a night.

Here is the Python class I wrote to control the LCD:
http://cvs.sourceforge.net/viewcvs.py/mpy3/1.0/pyCFontz.py?rev=1.2&view=auto

I just posted my other project related to the tunes box <a href="http://ofcourseitworks.com/content/view/13/2/">The Tunesbox Oscilloscope</a>. Its sort of an "Analog Visualizer" for the Tunesbox.

I do have an iPod now, but I still like a lot of things about the tunesbox better. I really wish the iPod could just read mp3 files that are written to it the way the cheap sandisk player I had could.