I doubt I could do any recommendation in this forum but you could always request for quotes or look for offers in the Offers forums.
But if you are anything like me and want to get your hands dirty with dedicated hosting, you might want to look at a Cobalt RaQ, they may not be all that powerful as compared to the other solutions around but they got a functional control panel and since they are standard hardware, you could always find easy patches from Sun and other packages like webalizer, openwebmail and so on and straightforward information on how to install any other add-ons.
Like I say, they are not as powerful as the other types of available hardware, but offers the best value for beginners. When everything stablizations, you may want to get root access to tweak the server along the way.
Of course, the other way is to go to a managed solution which generally is more expensive then the unmanaged.