Rotating music is a pain but with 79 GB you can't avoid it. However more storage means less frequency of rotation and more selection on hand at any time.

Streaming is best avoided where possible. It incur data charges and Spotify isn't free unless you don't mind listening to ads. You may also want to listen to your personally customized albums. Quality is another matter to consider.

In your case I would go for the 64GB if I haven't bought the 16GB yet. But since you've already bought the 16GB using it with some inconvenience is also not a bad option.

Sorry to add to your confusion.