Online wallets? Too many horror stories.
I'm going to second this. Online wallets are far too risky. Even with a legitimate site, it can be hacked, an employee can go rogue, etc. You're basically opening yourself up to a lot more risks than you would be otherwise. Unlike cash, which is FEDERALLY insured when in a bank, your BTC, if stolen/hacked/etc. is gone forever. Always keep it in your own possession at all times.
Weird how everybody chimes in to online wallet bashing while the poster asked specifically about two non-online wallets (mycelium and electrum) that keep wallet data (private keys) local while using online services to access the blockchain. These wallets are just as safe as a standard bitcoin-qt wallet but need much less data storage and transfer capacity. Of course they rely on external services to access the blockchain, but at least mycelium allows one to export private keys into some other wallet (don't know about electrum but I think it has similar features.)