Alright guys… I’ve solved my own problem. I’ll put the solution here in case anyone else has this issue. I’m surprised it hasn’t been mentioned before.
Anyway, the 16GB card I have is just fine, even though it’s just a class II card. Also, the number of songs I have (>2000) is also perfectly acceptable by the Fuze. The issue, I believe, arose from the method I used to transfer all the songs.
I had originally transferred all 2300+ songs via MSC. The media refresh took a good solid 10 minutes or so. Everything worked except an unusually long pause before loading any track.
In order to fix this I formatted my card in Windows (fat32) and then transferred all my songs back to the card, but this time in Windows Media Player using MTP mode. After this finished I noticed the media refresh took much less time (maybe 5 minutes) and the long pause before loading each track was gone! Now switching tracks takes less than a second.
So for anyone who stumples upon this having the same issue, it seems the Fuze likes songs transferred via MTP a little better than MSC… or at least it is able to load them up faster.
So there you have it… go figure.