Well, if your site is to the point of needing a dedicated server, RAM is going to be your biggest friend. The PIII 1ghz won't be too bad, but the slower chip with not much ram may not leave you much room to grow.
Setup B would be great, if it had 1 GB of ram. See if you can upgrade maybe?
As far as prices, those are pretty much in the ballpark for dedicated servers. There are lots of little things that can make a price lower or higher, etc. Also, dedicated servers tend to leave you pretty much in charge. So if you have no idea how to adminster or work in a linux environment.. you may want to find a server provider that is at least semi-managed, so when you have a problem you can still get help in resolving it.