So you basically pay "rent" for some space in a big company's data center. You can rent one machine, or sometimes an entire cage; sometimes you can rent the cage without any machines and put your own in there, but it's kinda pricey, I'd think, as thorpe mentions.
In NYC, two companies with good reps are NYI (New York Internet) and Pair.com, both of which do co-lo AFAIK, and also AFAIK they do hosting as well ... if your trouble isn't with them 😉 you might see what they have to offer. Both of them are pretty supportive of open-source in general.
Finally, if any of your sites are for real brick-front business, what about putting the server there? Some small/medium businesses have bandwidth to burn, and if it's there site, there might be some incentive ... maybe you could work out a "deal" ....
Finally, in re: security. You've got to have a little experience, I'd think. Running a "test site" on your home connection might be good practice ... but check your ISP's TOS; many expect higher rates for hosting a server 😉