We actually prepackage a recent blockchain with the app when you download it. So it only needs to udpate the last bit the first time you run it (< 1 minute over wifi). After that future updates are near instant (a few seconds) over 3G or WiFi.
One obvious question: is there anything to prevent someone from repackaging this, as it's open source, and modifying it to rob folks?
This relies on trust.
Does anyone remember Paypal updating their iPhone app last year to do SSL certificate verification because up until that point it was trivially MITM'able?