The key might be this ... 'a good shared hosting plan'. Yes, you might have hosted there for years and all previously installed versions of Moodle worked but they were't 3.8.1+ ... which has an update coming out this coming Monday ... ie, tomorrow.
Also, this ... '(kept the top level folders so as to hopefully avoid new permissions errors)' ... does that mean code is to go into a subdirectory and you kept any all things above that subdirectory? Are ownerships/permssions on the directory you are creating the same as directories above the moodle code you are installing?
Have any .htaccess files in any directory? If so, what do they look like? Those come into play in a sneaky way! :|
What are ownerships and permissions on the data directory? Yep, I know you said provider check those, but did you?
You've made no mention of what web service using? Apache with mod, Apache with fastcgi/php-fpm or what?
Might be related to this 'cannot create local file pool'.
Having said all that ... you could possibly try manually removing the contents of ... that's contents of ... your moodledata/localcache/ directory. And try it again. Moodle does try to cache right away - as seen in lines of your error debug.
'SoS', Ken