I am with a host at present, which was £54 for the year. Unlimited bandwith, Unlimited storage, and so on. But I want a dedicated server so I can have much more control over it and run scripts hourly. Plus I was having issues with how reliable my Mysql DB was.
Do you really need a dedicated server? If you just want more control you might want to consider a virtual machine instead - such as those offered by Bytemark (I use mine for backup mail/DNS, it's very reliable and the staff are helpful).