First off, there is no such thing as an NSA-proof phone. If they put Stuxnet on airgapped Iranian computers, they sure as fuck will be able to hack your networked phone if they want. That said, they probably don't want to expend the extra effort to do so, and if you're just interested in opting out of dragnet surveillance that's pretty practical, albeit not without sacrifices.
There are two key elements to private communication: end-to-end cryptography and secure endpoints. If you have the former, but not the latter it is trivial for the malicious code on your computer to retrieve your encryption keys or the unencrypted plaintext data of your communications. If you have the latter, but not the former, it is trivial to intercept, store, and analyze your encrypted communications.
The problem with most non-Android-based mobile OS is that they lack good software for encryption. Sure, I trust the code on an Ubuntu phone more than stock Android, but I don't have access to apps like CSipSimple, Orbot, Orweb, ChatSecure, and APG. Simply put, the best cryptography software is almost exclusively written for Android. But we can't trust Google, a participant in PRISM and a company whose business model is centered around spying on their uses to target advertising at them (and to sell that data to other 3rd-party companies).
So here, IMO, is your most practical solution: use Replicant on a GTA04-based phone without any non-free Google services and download a minimal number of trusted applications from F-Droid. If you can't find a GTA04-based phone, I'd go for the Samsung Galaxy III (has to be the i9300 version I believe), but the former is preferred because this phone lacks the strong modem isolation that the GTA04 has. Both use non-free (read dangerous) modems, but the GTA04 was designed to mitigate the access of the modem to your HD. A Replicant dev. actually uncovered a backdoor in the Galaxy series that allows the modem rw access to the HD and then patched it, but their could be others they missed. Of course, there is no such thing as perfect security, and I would certainly say the S III provides reasonable security w/ Replicant. It is much more attractive too in terms of specs.
Replicant is based on Cyanogenmod, which contains non-free libraries that helps it support a much larger range of phones. Cyanogenmod seems to be a lot less secure/private in my experience though. For example, just to get the phone to stop connecting to Google's servers I had to firewall the kernel itself with AFWall+, an iptables front-end. If having a modern/fast phone is important to you, the Galaxy S III should be pretty similar to your iPhone and I would just go with that and avoid the Cyanogenmod mess.
So, in recap:
Phone: GTA04 or i9300
OS: Replicant
Full disk and SD card encryption