I have downloaded and tried to install a couple of different free themes.

I get this error each time though,
"Could not find a Joomla! XML setup file in the package"

Any help on what the problem is would be appreciated.

(When I unzip the pkg, I see the xml in it)

Have you tried the FTP approach, i.e. extracting folder /template_name and uploading to /templates ?

Yes, I did. It tells me:
Installation file not found.

Which specific templates are you trying to install?

redevo_aphelion- I am having the same issue with any template I try to install though : (

I am unzipping the file on my hd, then ftping it to the /templates
dir.
From there I am going to
Installers > templates Site

In the Install from directory form field, I am entering
"fullpath"/templates/redevo_aphelion/