The new phone came with standard Android, so I've so far added
Prime Dice, for polyhedral dice rolling during roleplaying games
Greenify, a battery saver. It does just one thing, puts apps into hibernation when the screen is dark.
SyncMe, for transferring photos to the computer
And yes, I had malware already despite only downloading from the Google Store. A screen asking to install 'Facebook Patch 4' was popping up after boots - and I don't have Facebook installed.
[added] Two anti-virus apps found nothing but the third - AVG - said to disable a preinstalled Google looking file and that worked.