1. Cache the media library directory structure on the device. If I'm in an area with poor reception, it can take a long time to just browse around on my phone and pick files to play that I already have cached on the device. It would be nice if Subsonic cached the directory structure on the phone (either the entire thing, or just folders I've visited). Subsonic could simply keep track of the last modification date to any given folder so it would know when to push updates to the phone. This would REALLY improve the experience of using the Android client.
2. Cache album/artist art thumbnails. I can tell the little thumbnail images are getting downloaded each time as I scroll through them. This doesn't really slow things down that much, but it does eat bandwidth (which sucks for those of us on limited plans /glare at&t

3. Allow the user to choose the location of the cache. I'd like to be able to place the Subsonic cache on an external SD card, which is not possible on my phone (or perhaps I've overlooked the option?)
4. Error correction. Maybe not really cache related... but occasionally my downloads get corrupted if I'm moving around between areas of good/bad reception or if I'm downloading on Wifi and the connections drops out (anyone else have this problem?). To workaround this I just go delete the file and let the client re-download it. It would be nice, however, if the player could maybe do an MD5 hash comparison of the data or something like that, and then re-cache corrupt files automatically. I guess that might be asking a little much because it's pretty complicated...
I actually just noticed that the Android client source is in the SVN repo, so I might take a whack at implementing these myself if I have the time this week. Anyways - just thought I'd through in my two cents. Again, love the product, and I hope it continues to improve!