I have good experience with
Slicehost. They are very very flexible. The contracts are on a monthly basis so if you dont like what you get for your money you can end you contract each month. If you want to upgrade or downgrade, thats also possible on a monthly basis. I dont know about the CPanel, I do everything from the command line but I know they have developed their own control panel.
One warning: you absolutely need to have the know-how to administer a Linux box. They give you a choice of different Linux distro's but then you get the bare minimum: a Linux box with SSH but if you want Apache or a DBMS you need to install and configure it yourself.