Thanks for all the feedback, here are a few answers...
Install size: we are aware that the game is 'on the heavy side'. The base game engine we are using (Unity) takes up 9megs, and since Android will install all native compiled code to the internal memory by default, that is what the basic footprint is. There might be room for optimization in the future, but for now we can't change it. Also, we are using 1024x1024 images for all backgrounds (in order to fit all screens). One image (compressed) is 0.5MB, so with 14 themes, you do the math... not going to fit in 1-2megs
We never really had to worry about memory on the iPhone side, so this has been an eye opener for us.
Galaxy S: we thought it would be easier, but apparently the device has some 'funky' memory management and is not freeing up enough space to run our games. Again, Unity is trying to find a workaround, but unfortunately we don't have an ETA at this point.
Global leaderboards/Challenges: on the iPhone, we implemented Facebook connect, but hardly anybody was using it. I think Openfeint has potential and should be coming to Android soon... we'll see.