I wanted to report back: I ended up getting a Samsung Galaxy S (SGH-T959) which has 16GB internal and put in a 32GB card. With the Voodoo Sound Plus app, it does sound great. It's not as small or light as I was looking for, but it's still pocketable.
What are you guys who have Android using for players? I have tested a few that say that they are gapless, but aren't on this device. GoneMAD works and is pretty nice. I don't typically use EQ or need fancy skins, etc., just looking for a basic, gapless player.