I've been making some tests
I was using the Peakblue theme on the Sansa Zip.
Then, I switched to the Blu theme, who HAS album art and I found out that it doesn't lag!
When you press next, the music stops suddenly and then the track changes quickly.

<= Peakblue | Blu =>

After some trials it seems to me that the laggy themes are not the ones full of images, with album art or some other things, but the ones with the peak meter!
That's strange, my old Clip+ handled the peak meter like a charm!
Any ideas about that?