Rockbox

CDG+mp3 Karaoke is the Number 1 format in which Karaoke files are found online... Players exist on all platforms, including winamp plugins, etc... CD+G Karaoke discs are the standard, and CDG+mp3 is the ripped format that is commonly used.

The CDG spec is quite simple, only about 8 simple blitish commands,
and GPLed C code exists already, so this would be a relatively simple plugin that would ideally play the mp3 with the same name as the cdg file, as they are typically stored together. Blitting to the screen, scaled of course, is the only really functionality needed, and it's certainly lower bandwidth than mpeg, so all cpus should be able to handle it in a timely manner.

This would add a nearly full karaoke playback system to Rockbox...
The only possible lacking thing would be also recording the microphone for singing results for later playback, if desired, and that's a future dream item.

Original spec for CDG decoding:
http://www.jbum.com/cdg_revealed.html

GPLed c code which implements the above:
http://www.makenai.net/gpoke
(This doesn't have mp3 decoding, making it perfect for a rockbox plugin... it's only the cdg playing)