What security features are important when buying a smartphone?

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.

One of the key aspects to consider for this is the support/patching policy of your mobile device vendor. If you're planning to keep the phone for say 2-3 years you don't want it to go out of support after 18 months.

Unfortunately this can be quite tricky information to come across with many vendors not providing published support lifecycles.

Also complicating the picture is that some device combinations have long "support chains" where multiple companies have to collaborate to produce patches. So for example an O2 Samsung Android phone, might need 3 companies (Google, Samsung and O2) to co-operate to provide a patch. This kind of process inevitably leads to slower patching.

Likely the best approach to this would be to choose a device which has the smallest possible chain, so either an Android device from Google, an iOS device from Apple or a Windows Phone device from Microsoft, and in all cases an unlocked device is likely to get faster patches than one from a carrier.

The other answers regarding encryption are great. I'm going to approach this question from the tinfoil / dissident angle, as I believe it's valid for nearly every scenario... but I still want to explain my reasoning, and how I came to these conclusions.

All of the problems I'll discuss are routinely exploited by criminals, and repressive governments. In some countries, being a member of a certain religious order, or the wrong race, is enough of a reason for the authorities to schedule your unapproved organ donation:

There are reports of systematic torture, illegal imprisonment, forced labor, organ harvesting and abusive psychiatric measures, with the apparent aim of forcing practitioners to recant their belief in Falun Gong.

A removable battery is a must

This is at the top of my list: you want a smart phone that has a removable battery.

Why? Because there are a million ways to hack you and listen in on your conversations. Imagine making sweet love to your significant other, and some sick bastard from a repressive government, or even a criminal, decides to listen in and get their kicks:

“In the course of their daily work they stumble across something that is completely unrelated to their work, for example an intimate nude photo of someone in a sexually compromising situation but they’re extremely attractive,” he said. “So what do they do? They turn around in their chair and they show a co-worker. And their co-worker says: ‘Oh, hey, that’s great. Send that to Bill down the way.’ ”

Mr. Snowden said that type of sharing occurred once every couple of months and was “seen as the fringe benefits of surveillance positions.”

There are also many ways to pretend that your phone is turned off when it really isn't off:

Your phone basically becomes a bug that tells the NSA everything going on around you. Any conversation you have or any embarrassing thing you do, the NSA will have it recorded.

The worst part is that even if you turned the phone off to be safe, it wouldn't really be off. The app makes your phone pretend to be off — it turns off the screen, ignores incoming calls and doesn't respond to button presses — but the spying will still be going on.

As we see from the above example, your privacy is not even respected by the NSA. Criminals and repressive governments can also hack your phone and listen in on your conversations. So why wouldn't you want a phone with a removable battery if you feel you're being targeted?

Find a device that's easily moddable

Free apps on Android can easily allow a form of backdoor access to your phone in it's entirety. You know all those creepy permissions you keep accepting because you like "free stuff"? Yeah, those. "This application wants access to your: contacts, microphone, camera, etc." No thanks.

It's even worse when governments and advertising companies use ultrasonic tricks that link your devices together. A removable battery, along with Cyanogen's Privacy Guard, will go a long way towards combating this.

How can you expect to keep information secure if your phone is constantly sending information about your usage patterns to marketing companies, and governments? Don't forget CISPA. The government wants to request that data legally, even though they already have it.

The government can't even keep it's own information secure, so why should they be allowed to keep your information? Companies can't seem to keep their data secure either. Why should you trust either of them?

I would suggest a phone that can be modded. For example, you can Install CyanogenMod, and use their Privacy Guard feature to disable app access to your important information.

You also have much more control over your phone than with the stock crap.

Carrier locked phones are worthless in the USA, and China

You don't want a phone that's locked to a carrier. There are often severe delays on security updates, some taking years. One of my phones was carrier locked, and I couldn't update it until four years later. Meanwhile, it was vulnerable to almost everything, but it proved to be an excellent honeypot for reverse-engineering purposes. I suspect you may not want something like that.

This is still a problem with a lot of carrier-locked phones. You'll notice you entirely missed out on updates that everyone else is getting. Not good.

Unfortunately, this usually means shelling out full price for an unlocked phone. It's definitely worth it, as you can update the phone far easier - especially if you're using CyanogenMod. When the phone is entirely in your control, you can do more with it. You can apply security updates faster, and you don't need to wait for the carrier to update it.

Too Long, Didn't Read

My top three recommendations:

Removable battery (apps/hacks can fake your phone being off when it's really still on)
Moddable with Privacy Guard (Cyanogen Mod, for example)
Unlocked phones, no carrier locks.