Rockbox all the way, my library is +4000 songs and I can scroll from 1st to last in seconds, something that takes an age on the stock player.

Also I find the random, much more random than the stock player. For some reason the stock player always seems to play some tracks loads more than others (which it shouldn't when the library is so big)

As mentioned previously the UI could be better, but I believe the project is still bing worked on ( and you create your own)