To give you a short answer, yes, I think those specs will be more than enough.
We currently rent 3 machines and push about 250GB/mo through them by hosting about 1500 domains. With PIII 1133MHz and 512MB Ram the servers basically sleep. Load between the servers runs about 0.50 on average and CPU is used at 15% or less.
Bandwidth on a single site shouldn't need more than what you propose, and if you say your load is low, reducing it by 256MB won't impact it that much either.
Overall, those specs are fine and I'm sure you can find a TON of providers out there that will meet your needs. Dialtone is the only one I can suggest based on experience, but I have heard a lot of good things about Rackspace and Fastservers (in fact, I'm signing up for FS colo next week)