What are my options for storing NXT outside of a centralized exchange?
In the blockchain through the client.
If you don't want to download the blockchain, try mynxt.info or mofowallet.com. mynxt.info also have andoid and iOS apps.
I'm very careful about what I install on my computer. Can I install NRS in a sandbox somehow? I suppose I could run it as a very unprivileged user. I use Linux BTW.
I think a web wallet is too risky.
Would Jay be a good choice?