Is there a good place to get nice cPanel themes? Free or otherwise. I am interested in building my own but there seems to be too many hooks into cPanel embedded in the HTML.

Well you can BUILD your own using RVskin (i think its possible)
OR
google for "FREE+cpanel themes"...

Well i have found those guys offering cpanel themes:
- http://www.lypha.com/cptheme.shtml

I recommend you to HIRE some freelancer do a custom one for you (just my advice).

Yes, you can build your own which will make it more custom to your web hosting company. You should fine a designer / developer skilled in the area so nothing gets messed up as a result. Best of luck!

RVSkin is the best solution. It allows to customize Cpanel and includes different themes and have support a lot of languages.

Cpanel just released some new free themes at http://cpanel.net/themes/
You can download the theme tarball and just edit the html code in it for minor modifications.