I know this isn't a huge issue since I can obviously trust the NFO certificate, but this is really annoying whenever I want to connect/upload/download from the webhost.
Is there any way to bypass this? The boxes to "Always trust..." is grayed out, so I can't do that...
SFTP is definitely the way to go. This warning a signal that you accidentally used FTP instead of SFTP/SCP, and that your FTP client tried to (incompletely, since regular FTP is fundamentally problematic) secure it using TLS.
You could instead switch to use standard FTP instead of one of the TLS-enabled wrapper variants, but that's not as good as switching to SFTP.
Arguably, we should stop supporting FTP entirely for webhosting accounts. The only reason not to would be that it could break legacy applications.
Good to know. I believe I was letting FileZilla connect with a default port (which I'm guessing is 21). I'll try it with 22 next time I need to change something!