I would guess you want to look for a Virtual Private Server or Virtual Machine with root access.
In my (commercial) opinion, hosting technologies either fall into the category of a "completely standardized" hosting environment (e.g. Apache/mod_php for PHP) or they don't. Lots of companies provide PHP hosting in exactly the same way. But for most newer hosting platforms like Python and Ruby - they don't, and so hosts have to go to a lot more work and domain expertise to make particular hosting environments for those languages.
Therefore if you shop for a Python-specialising host, you ought to find a much more clued-in host than one selling PHP hosting. However I would expect you'd have to pay more for that rarer expertise. The risk is that you get something a bit more half-baked or very specific to a particular host, which makes your deployment less portable should you want to move.
Instead if you shop for a VPS / Virtual Machine you will get a product that is broadly similar across thousands of hosts - root access, bandwidth, disc space, and the ability to install the exact software, versions and modules you want. You may have to learn a bit more to set this kind of thing up, but you won't have to submit to one hosting company's idea of what a "standard" Python environment is. Make your own environment, one that fits your application, and you'll have the pick of many more companies.
I may be overstating the case for VPS slightly, as I'm thinking more about past horrors of Rails deployment, where I have specific experience :)