These are called "co-location facilities" and are pretty plentiful in the larger areas. What state and city would you need the co-location to be hosted in?
For a single server, most data centers will have a lot of cost overhead, because you don't get just power and "a LAN" -- you actually get defined rack space, in a locked cage, with connectivity that you negotiate with whatever ISPs are available in the center. You can get what you want, it justs costs a lot for the first rack unit.
If you separately need a link to another premises, most ISPs will be able to lease fiber between the co-lo and your premises. Again, this may have significant installation costs. Another option would be to set up a VLAN over the publicly routed internet.
I've previously heard of hobbyist-oriented co-lo facilities that have "shared racks" and "shared uplink," but I don't know of any specific names right now.
If you can use "someone else's hardware" then you can use one of a zillion self-managed server hosts (serverbeach, rackspace, interserver, etc) which may still be better than a virtualized cloud option for performance reasons.
Some co-location facilities you may want to check out:
Hurricane Electric
Internap
Digital Realty Trust
Equinix
AT&T (finding the right part of AT&T to call may be a chore though :-)
For example, looking at the Equinix data center in Palo Alto:
http://www.datacentermap.com/usa/california/palo-alto/switchdata-palo-alto.htmlThey offer "hosting of individual servers" which seems like it might let you get away with less of an initial setup cost.
Similar locations exist all over the country, with better selection in major metropolitan areas.
