Blockchain just came out with a great Android client, based on bitcoin-wallet.
In the description it says "No blockchain downlaod [sic.]". However, in the documentation of their sources, they say "When run for the first time, the block chain needs to be downloaded".
I'd be optimistic and guess they download all headers, and fully check the transactions regarding the local wallet, ignoring the unrelated transactions. However this is just a guess and I'd like to know which checks does it actually do client side, and how much does it instead "just trust" blockchain.info (which is very reputable anyway, but still I'd rather know).