TLDR: There are several categories of security you must consider when looking for a phone. The main advice, though, is to get a newer phone with the latest security features, and from a manufacturer that has a good reputation of providing updates.
Security against other people (peers, police/government)
Look for newer devices with full disk encryption, and at the very least have a code or fingerprint required to unlock your device.
Both Android and iOS have the ability to encrypt the phone. When booting the phone, the password must be provided to finish booting and to view files.
- Upside: Your phone is protected from external attempts to read the data
- Downside: You must type in your password/PIN every time you boot, and usually every time you unlock your screen.
As this is built-in to more recent versions of Android and iOS, you must slightly narrow your search to exclude older phones that don't have this capability.
Encryption key vs unlock code
As a usability/security tradeoff, I prefer to have a long password required on boot, but have a simpler code to unlock the screen. Apple does this natively, letting you set a PIN or password required on boot, but thereafter letting you unlock the phone with your fingerprint.
- Upside: You can use a complex password, while keeping the ease of unlocking your phone quickly.
- Upside: A shoulder-surfer can't unlock your phone, since your fingerprint unlocks it. They would have to catch you as you type in the password on boot. (When you type your password, be sure no one is watching!)
- Downside: Your fingerprint is not protected by law (in the U.S.). The police can force you to unlock the phone with your fingerprint. Whereas a password or code, something you know, cannot be forced out of you. Even if a court orders you and holds you in contempt for failing to provide the unlock code, they cannot access your data without your cooperation.
On a rooted Android device, you can install a mod that lets you have a complex boot password and a simpler PIN for the screen unlock. If you enter the PIN incorrectly, it requires the strong password to be entered, which prevents brute-force attempts at the much simpler PIN. You are losing some security, however, since anyone shoulder-surfing could see you put in your PIN and later steal the phone for unlocking.
- Upside: You can use a complex password, while keeping the ease of unlocking your phone quickly.
- Upside: Only your knowledge can unlock the device.
- Downside: You must enter a PIN every time you unlock the screen. As this happens frequently, it is much more likely that someone could find out your simple unlock combination.
Security against apps
Check app permissions before installing, and make sure you get a newer phone that has extra permission management.
Apple/iOS
Apple devices (excluding jailbroken ones) can only install apps that have gone through Apple's vetting process. While this isn't 100% successful, it does protect most users from installing a malicious app. On top of that, certain obvious privacy features, such as GPS location and contact info, require an extra user prompt to allow an app to access that information.
Android 6.0+
Android permission settings before 6.0 Marshmallow were all-or-nothing. If an app requested permissions to your GPS, you either allowed it or didn't install the app. Android 6.0 introduces similar features to iOS that let the user deny certain permissions while still installing the app.
If looking at Android devices, this narrows the eligible devices, excluding phones that don't have Android 6.0 or newer.
Android 4.x-5.x with XPrivacy
However, if the Android device has root and can install the Xposed framework, you can install XPrivacy. That app overhauls the permission model on Android so that nearly every possible privacy-related permission can be allowed or denied in real time. If the app tries to use GPS, it prompts you to allow or deny (or provide fake/null information). This is available to most rootable Android devices running any version of Android 4.0 to 5.0.
Look for a phone that can be rooted if you want extreme privacy permission tweaking.
Security against bugs/exploits
Look for phones made by manufacturers with a history of regular updates.
Most iOS and Android updates include bug fixes along with new features. As long as the iOS device is supported, they can all get the update at the same time when it is released.
On Android, Nexus devices are generally the first to receive updates. For other manufacturers, make sure they have a history of providing updates to older phones and within a reasonable timeframe.
Alternatively, find an Android phone with an unlocked bootloader and an active development community. While more technical, this can be the fastest way to get the latest updates, even after a manufacturer has stopped supporting the phone.
Security against the device manufacturer
Buy devices from a trusted manufacturer, and make sure it uses full-disk encryption where the manufacturer does not hold the key. Also, for Android, consider a device with an unlockable bootloader to be able to load custom ROMs with newer security updates and better privacy features built-in.
Apple devices cannot be unlocked even by Apple starting in iOS 8. While it may be possible in theory for Apple to provide an update that subverts this, currently it is impossible for Apple to unlock your phone or gain access to the encrypted partition on your phone. If you have iCloud Backup enabled, however, that data can be accessed by Apple.
Similarly, Android devices with Full Disk Encryption enabled cannot be unlocked by the manufacturer, or even Google.
Unlocked bootloader
With Android devices, an unlocked bootloader lets you install custom ROMs, or even make your own built from scratch using the Android OS source code. If your phone is no longer supported by the manufacturer, you can still update to the latest version of Android, assuming someone has compiled a Rom for your device.
Some Android ROMs have additional security and privacy controls built-in.
Warning: This can be detrimental to security. Make sure to use a Rom that is widely known and trusted.
Security in the cloud
Use a cloud storage provider that encrypts your data and does not have access to the unlock key.
Almost all cloud storage (Dropbox, iCloud, etc) store files in a non-encrypted way, or in a way that the cloud provider could decrypt the files without the user's permission.
The primary way to protect against this is to not use cloud storage. If you need to back up your files, use your own encrypted server or manually copy files onto an encrypted desktop computer.
A few storage providers, such as MEGA and SpiderOak, do encrypt your files. The encryption key is not accessible to them, and a government entity would have to coerce them to write an update to their software in order to acquire the unlock key from a user.
Android and Apple both have apps for MEGA that work similarly to Dropbox, including automatically saving photos taken by the phone.
Security against networks
Make sure your phone can use VPN software, and possibly use TOR to increase privacy. And be sure to browse the web with https when possible.
The internet service provider can view all of your unencrypted network traffic. To help avoid this, use a VPN. Note: the VPN can see your unencrypted data as well. Use a trusted VPN provider.
The ISP can even determine some information from encrypted network traffic, if you aren't using a VPN. If you open a web page that uses https, the ISP can see which domain you are going to. They cannot, however, see the specific page you are requesting, nor the data of the page itself.
If extreme privacy is a need, Tor may be the answer. It has plenty of downsides, the primary being slow speed (compared to normal browsing). But when using Tor, your ISP cannot see your network information, aside from the fact that you're using Tor. And the nodes on Tor are unable to know both the source (you) and destination (the website) due to the way the protocol is designed.