You just have to configure the server to require TLS (No version of Terminal Server/Remote Desktop supports SSL; they're misusing this term so laymen will understand, hopefully) .
You need a certificate. You can setup Certificate Services on the server and issue your own, more work than it's worth for one certificate. Or you can get one from one of the Free Certificate Authorities. Or you can use a paid CA as you mentioned in the Question. In any case make sure the Subject Name (SN) is the DNS name you use to remote into the server.
Install the cert, the CA should provide directions. Short version: run
mmc, add Certficates snap-in for Local Computer, under Personal Certificates, import the pfx file from the CA.
Then configure the server to use TLS and the Cert. Open the Terminal Services Configuration mmc, Connections, Properties, Edit Certificate, set the certificate to use and use TLS (might be called SSL here too, 2003 is an ancient system I haven't used in a while).
Official How to configure a Windows Server 2003 TS to use TLS for server authentication
The Common Name (CN) is the name that appears on the Certificate you get from the CA. This name must match what you enter to connect to the server. For instance you might be using server1.example.com. When you run "Remote Desktop Connection" and it asks for the "Computer" to, whatever you type in there must match the CN. If it does not match, say you type in an IP (which most public CAs will not issue a cert for) you'll get warning message every time you connect. That warning message can be turned off, but that would defeat the purpose of all this.
Being in a workgroup or a domain makes no meaningful difference. The only minor difference is that in a domain a server must have a full DNS name already (ie. the
server1.example.com above); where in workgroups computers can be addressed by their NetBIOS name only (
server1 in the running example). So you might have to figure out what domain name to use. If you don't have a domain name at all yet, you'll have to acquire one (this is a DNS domain name; not Active Directory Domains; I know, poor name choice).
The "Configure the server to use TLS and the Cert" are two on-screen options you'll see in the dialog. There will be a dropdown box listing the available certificates, and another dropdown box listing available security options (one of which will be Require TLS; or something similar).
If this is all well over your head, you might want to contact a local consultant. Getting this setup should take about an hour or less, and would be a great way to evaluate a local company's competency.