GoDaddy recommends I change my WordPress site’s hosting to improve email deliverability. Should I do so or use a transactional ESP instead?

I don't think you need to use a Virtual private server at this time unless you are getting so much traffic that GoDaddy is limiting you.

Here is info from Wordpress about email forwarding:

https://en.support.wordpress.com/email-forwarding/

Seeing as you probably bought your domain, I really suggest a Google Apps for Business account, because even though it is Gmail, your emails will come to whomever you send to as from your domain. There are a lot of other features with it as well, you can look at it from here:

https://apps.google.com/intx/en_us/products/?utm_source=google&utm_medium=cpc&utm_campaign=na-us-en-apps-bkws-gafw-trial-e&utm_term=google%20apps%20for%20work&KWID=43700007880944900

If you need any help, I can for sure help you with your email, as well as work out how to get Wordpress to do what you want. Even if you don't go with Google Apps, there are lots of other ways to get done what you need.

For sure though, if the current emails are being marked as spam for your users, or not even getting delivered that is not good for your reputation.

You could fix your email issues using Transaction ESP, like SendGrid.
Install this plugin in WordPress https://wordpress.org/plugins/wp-mail-smtp/
Which switches all emails to use SMTP and you set it up with your ESP's SMTP credentials.
I do this a lot with sites on cloud instances and it works very well.

On top of that, using an ESP like SendGrid you can actually see statistics of who is getting the email, bouncing, opening, etc... Great stuff, especially for a online business.

Going through your question and detail I could see you are having this same issue now which I faced few years ago with my WordPress setup.

For information all shared hosting provider use default linux SMTP to send outgoing emails which use sendmail to deliver emails and most of the time they miss-out important sending domain configuration like SPF, DKIM, DMARC records. And impact email delivery.

Don't worry about this as these can be easily fixed with following setup.

In order to fix this, you should use SMTP relay like ( ESP ) to deliver email externally, but here you should configure following important records on your email sending domain name:
SPF record according to your SMTP relay provider
DKIM record according to your SMTP relay provider
DMARC according to your sending domain name

Apart from above also configure your email sending domain name to your Google Postmasters account ( This is like Google webmasters for emails ).

This technology setup improved my email to all subscribers and my email open rate boosted from mere 17% to 48%.

Coming to SMTP email service provider, looking at your requirement, I would recommend to use SendGrid or SparkPost. SparkPost is quite easy to configure.

After above have been properly configured and aligned with your domain name, you should install https://wordpress.org/plugins/wp-mail-smtp/ wordpress plugin and add your SendGrid / SparkPost configurations.

I know these may sound little tricky for you. Let me know I can help you with complete setup within few minutes.

Wish you the best for your success!