We've got a GoDaddy dedicated host for $79/month. Bottom of the line model: I believe it's a 1.6GHz Celeron with 1G of RAM or something like that. It's perfect for straightening out the last few deployment issues and seeing if we can get traction before investing a lot in the site, though. We've got full root access to the box.

aplus.net has dedicated "value servers" for $50/mo. It's just last-generation hardware, but it's more than enough for me (for now).

I have had pretty good luck with these guys:

http://layeredtech.com/dedicated-servers/specials.php

slicehost.com. Dedicated box for 20/month. 70/month for 1GB.

Slicehost is a Xen-based VPS, not dedicated. The difference between them and other VPS providers is that they do not oversell each box so you get a good price/performance ratio.

I'm still on the waiting list for slicehost. Is this common or am I doing something wrong.

This is common. I've heard that some are waiting many weeks (or even months) to be granted a slice. The slicehost folks have recently introduced an option to prepay for your slice, bumping you up the queue.

I was lucky to get a slice the moment I signed up for it (early adopter I suppose). I have been very happy with their service.