Digital jukebox device with improved karaoke-related user interfaces, and associated methods

A jukebox device, comprising:

• processing resources, including at least one processor and a memory;
• and a touch screen display device, wherein the processing resources is configured to present, on the touch screen display device, a first set of screens that each list at least a portion of instances of media available for playback via the jukebox in a manner that resembles a book having multiple pages, each said page including at most a predefined maximum number of entries corresponding to a subset of instances of said media available for playback via the jukebox, and each said entry indicating at least a name associated with the corresponding instance of media that is selectable for playback via the jukebox device, and wherein the first set of screens each include a common set of control elements for controlling the book, and wherein the jukebox is further configured to dynamically rearrange, when an input is received indicating a letter for a song name or an artist, the listed portions of the instances of media such that ones of said entries starting with the indicated letter are listed starting at the top of a newly turned page in said book by dynamically reformatting the newly turned page to cause said entries that ordinarily would not appear at the start of a page to be adjusted accordingly to start at the top of the newly turned page.