You *could* start off with a top of the line VPS from a place like ServInt.
http://www.servint.com

However, if you want a full dedicated server, I'd say go with EV1Servers or SoftLayer.
http://www.ev1servers.net/Dedicated/
http://www.softlayer.com