I'm very new to BTC and I'm having some problems to understand why colds wallets are so important to users
In a big company that handles a lot of BTC I could understand, but for me I can't even think in a good reason to use it.
I use a blockchain account just because I started there and don't want to get rid off it yet and this account have little to none BTC, most of my BTCs are in my phone wallet (Bread for iOS)
More security is always better but you're right on one point: if the financial cost of security is greater than the value you want to secure, there's something wrong.
If you just have a few cents, no need for a cold wallet.
If you have thousands dollars, it's better to secure your btc with a cold wallet or an hardware wallet like Ledger, Trezor, ...
Could my phone be considered a cold wallet? Because it connects directly to the BTC network and (as far as I can tell) doesn't communicates with anything else (its a sandbox app that has no http privileges).
Short answer: No
And whats the point of sending your money to a paper wallet if anyone can still see the address and try to steal it? Isn't vanitygen capable of that? (takes time i know, but in statistic "if it can happen, probably it will someday")
As you wrote, stealing a wallet requires knowledge of the private key.
Finding the private key when you only know the address is "impossible" (understand "secured by cryptographic algorithms")
Therefore, nobody can steal your btc without access to your private key (let's forget a potential flaw in random number generators).
From what I see the only capable way of stealing a wallet is to get the private key, but why do people talk about cold storages like the money is actually sent? like fisically
You're right. No coin is sent to cold storage. This is just a misleading metaphor.
It only means that your private key isn't (and has never been) in contact with internet (stored on a computer connected to internet network)
Hope it helps.