For example with Bitcoin,Monero,Litecoin, etc I can generate a random wallet and put it in cold-storage, but from what I understand NXT wallets are only stored online?
NXT wallets are always in cold storage until you log in. Someone could steal your computer and your funds would still be safe.
Yes but someone could steal your coins without stealing your computer if your password is weak.
I don't see how any of this pertains to decentralization though
