I've got 2 servers co-located at £50 per month each (+VAT) - that works out to £117.50 per month, and upto 200MB bandwidth per day.
I am also considering co-locating a third server on another network - it costs £600+VAT for a year, including set-up costs if you pay for the year upfront, with 5GBytes transfer per month, but you have to wonder how much contention there is on their link (they have 18,000 clients apparently).
If you are co-locating, make sure you know the case size or format (e.g. microATX, 19" rack mount). Some places charge per u of rack space - this is about 1.5 inches.
Also, make sure you know what their policy is on visiting them - whether you have to pay for access at all times, or if it is free if you pre-book / working hours. I'd really suggest somewhere local. Of course, you could run FreeBSD with a wake-on LAN motherboard and never have to visit your machine to reboot it ;-)
The important issue is bandwidth. You should find out the connectivity of their network (who they peer with, how many hops to a backbone, etc), the size of their pipe (e.g. 2Mbps, 10Mbps, 1Gbps), how many other hosts are on their network (if possible) - and maybe also what content they allow - you won't really want your server to be on the same network as a load of pr0n sites, for instance.
Another thing: UPS, its good. If the area where the machine is hosted doesn't have many power outages, and those that exist last just a few minutes, maybe its less important (e.g. in the southeast UK there are very few power supply problems - touches wood).
Firewall - nice, but you don't know how well they can administrate it! Find out what ports they block.
Do they have dedicated traffic limiters, monitors, etc - bad for you if they have them, for the obvious reasons! Check out the extra charge per MB of transfer if you go over your limit!
If you are in America, 9NetAvenue (www.9netavenue.com) looked okay, but I haven't really checked them out thoroughly. If you are in the UK, there are plenty of official providers, and smaller ISPs who will let you colocate your machine for cheaper if you ask nicely.
Going back to Dedicated Servers (UK), here is a quick cut-n-paste of what they offer:
Rack space for your mini tower or 19" rack server
in our £1,000,000 million data centre.
5 GB of Bandwidth per month.
2 IP address as standard.
Free Server reboots.
Power connection through our Symettra
UPS and 250 KW Backup Generator.
Power and RJ45 cable from your server to
Your system goes to a dedicated port on
our Cisco network gear.
Access to your server by appointment.