I agree with Duster,
go with Catalog. You get what you pay for in this industry and at $120/month I don't think you are going to get a lot. I have emailed Christian Henning several times over the past month and always received a reply in a very timely manner.
If you think you will need regular support to get going than there isn't much of a choice. You can't put a price an good/great support (it's an endangered species it seems!).
And, Plesk comes installed and configured on Catalog servers.
If you don't need a lot of disk space / processing power you might want to take a look at
http://dialtoneinternet.com
They have a special right now for the following:
Celeron 333
6.4 GB IDE hard drive
64 mb ram
65 gb bandwidth
$177/month
Their server interface is pretty good and does what it needs to.
I have a similar server configuration and I have almost 100 domains on it and pushing close to 10 gb per month and I find it very fast. I would recommend putting the RAM to 128 like I did.
Or you might want to check out Daniel at
http://ultraspeedusa.com
He could put together a package that would more than suit your needs.