I can't answer the questions about exchanges from a UK perspective as I'm in Aus.
I've had no trouble with MtGox from here though. (well.. minor bank transfer issues sorted out in reasonable time)
For most exchanges I believe withdrawal of BTC is as simple as entering a bitcoin address and transferring your coins. Generally only takes minutes or less.
For a bitcoin wallet I'd recommend
http://blockchain.info/walletIt works in such a way that their web service doesn't actually have access to your unencrypted keys. (when you type your password, it decrypts it on your computer)
Make sure you either print out a paper wallet as a backup, or email a backup to yourself (which is also encrypted).