I'm working on something like that, for iPhone, but not really for generating, more for spending.. the problem is it's really hard to type in a bitcoin address on that little thing.
QR codes have been proposed as a solution
here.
This was my first though too, it would be nice if someone was able to do this for the android as well, especially when it should be very easy for the QR integration with the zxing library.
I dislike the idea of using a third party site myself, at least at the moment. I would much rather carry around a wallet on my mobile device.
A mobile client would really be a great bump to bitcoin overall, been able to go to large group events (LUG event, Con's etc) where there may be opportunity to make real world transactions in front of people who might otherwise be unaware of bitcoin, especially if they could download a app there and then and get involved.