www.godaddy.com with shared hosting (linux) with delux plan or unlimited plan I working at 100% (no permission issue and no DB privilige issue).
You can also use cPanel with
www.hostgator.com
cPanel has a limitation that require the support to grant the MySQL user.
We have a "baby" account at hostgator and they provide the support to grant the MySQL user.
You can also use cPanel with dedicated server (WHM) that have PHPMyAdmin with root login.
In this case, you can grant the MySQL User yourself.
There are other hosting companies that are ok.
You also have
www.ovh.com in france that propose shared hosting with 100% ok.
Your problem is more related to Plesk that is not easy to setup.
Also avoid solution with "Direct Admin" that is also difficult to setup.