So first you say linux is unsafe then you say you use linux because it's safe. Awesome!
Having professional experience in this realm, the problem is that Android is frequently modified by OEMs to meet carrier demands on insane deadlines. The core Android system is quite solid, if you get the code from the public Google repos. By the time the carries and the OEMs install all their 'cr*p' including carrier approved spyware (Carrier IQ, etc...), its a totally different beast. Remember, if the Carrier installed it its 'marketing research software', if someone else installed it, its 'spyware'. This is true for all the phones....
Worried about security, don't buy a device from a carrier, buy it unlocked direct from Google. As for the Google store, if its free, you should ask yourself why?