Cheapest + Reliable that I've used are Burst net and hostdime. Nowadays I don't use cheap dedicated servers anymore since I host mainly medium to big'ish companies' websites, so uptime, network and server maintenance are critical, but I can vouch for those two as reliable and good. I still use burst net for their VPSs, and I've yet to have a headache from them.
For managed dedicated servers, I use both WiredTree and DedicatedNow, though they're not cheap, just very very reliable.