I've got Cyberpunks Virtual Jukebox software set up with my home theater.
I have set it up on a machine with 2 video cards, one being an ATI all in wonder 16 (old card, but works for this purpose). So I can select the music and videos on the computer monitor screen (which will eventually be a touch screen, just not there yet). The videos output to my 55" TV. Sound is handled through my Home Theater system (6 channel, 5 subs, 1000+ watts, sounds great). If song is chosen, the album artwork shows up on the TV screen. You can even cycle through other picture files if you desire.
It looks and sounds great. Figure about 40-50MB for a good, high quality video (they are all between 3-5 minutes long). Anything smaller and you can see the artifacts. High Quality Divx videos look great, but my TV is not HDTV, a higher quality set will show more artifacts.