I have about 3600 songs on a 16GB card. The regular droid media player would take a good 30 seconds anytime I selected artist/album/genre. It does it EVERY time, not just the first time I loaded them on. I've had them on there for almost two weeks now. Even if I select an album, and play it, and come back to the library again, it still reloads everything all over again. Waiting 30 seconds everytime I wanted to choose a new album or song was unacceptable, so I looked for alternatives.
bTunes is the answer. The first time it loaded my library it took a good minute, but after that it's practically instant. Loading songs is instant. Loading an album is instant. Loading artists is instant. Playing is instant. If I click shuffle all with a good 1000-2000 songs, it will take a few seconds to load them, but that's understandable. At least I can browse my library without waiting. It also does a quick scan when you start the player after a reboot, but its only 5-10 seconds, and after that its good till the next reboot. I also think I sped up the scan time by selecting a specific directory on my card where the music is, so it doesn't scan though every file/folder.
Unfortunately, it's not free. But well worth it in my opinion.