Seems the more one discusses, the more detail comes to light.
So you: tried to update via SoftTac. Didn't work 100% - theme issue. So now you've deleted the updated SoffTac install. And installed a fresh moodle. How? Via SoftTac? And the issue hasn't gone away.
If that is correct so far, then the only conclusion one can make reading about what has happened so far is SoftTac installs of Moodle have issues.
Don't work for your provider ... who IMHO, is almost criminal ... telling you SoftTac upgrade will work by providing you a link/button to do it. And when customer tries it ... oops ... snafu! Did your provider help desk suggest you visit these forums for help? Hmmmm ... provider doesn't support what they offer customers. Like I said ..... darn near criminal!
Ok, so let's begin the guessing game ... you have cPanel. Find the moodledata directory and manually remove all files/contents in the following folders: cache and localcache. That's moodledata directory ... not moodle code ... and its the *contents of* cache and localcache ... not the folders cache and localcache.
Then, try accessing your site via browser again. It should be slower at first, moodle is attempting to update the contents of the cache and localcache folders as you click around, etc.
Now if that doesn't work, then this is the last thing I could suggest ...
edit your config.php file ... cPanel does have an editor ... that resides in the moodle code directory. I cannot tell you where the moodle code directory is located but probably in public_html.
In the config.php file add the following line ** right after this line **: $CFG->admin = 'admin'; on a NEW blank line.
$CFG->theme='clean';
Save the config.php file.
No need to restart anything, just use a browser and hit the site.
There is only one other option and that involves ssh access (cli) access to your server and running a command line only script to do the same thing ... purge_caches.php in moodlecode/admin/cli/
You did check out the environment when the site was a 3.5.1 to make sure your hosting environment could handle a 3.6.highest installation - minimum of mysql 5.6 and php 7.0.0 ... although if your provider is still running both of those versions they are providing you with software that is out of date and has reached end of life.
Ok ... that's all I can guess. Best of luck!
'spirit of sharing', Ken