I find it odd that a host would not already have the software installed (phpMyAdmin). To my knowledge phpMyAdmin comes auto-installed with the CPanel software as well as Plesk (probably a number of others as well). Personally, I think they either opted not to install it, they are just to lazy to install it, or they do not know what they are doing (either way, I would find a new host, phpMyAdmin plays a good role in a good deal of all PHP scripts, at least the ones that use MySQL).
Just my .02 -
- SaintDog