If you are looking to have your own box and get your hands dirty with Linux administration then slicehost is a great option for you.
My last hosting company didn't allow me access to log files and were just an overall pain to work with. I can tell you that if Alan Shimel had had my hosting company the guys that took over his domain probably wouldn't have had the patience to wait out what it took me to move mine...anyway I digress.
Slicehost is great, here is a breakdown of their plans:
RAM PRICE HD BW
You start with a slimmed down version of one of the following OS's"
Debian 4.0 (etch)
Ubuntu 7.10 (gutsy)
Ubuntu 8.04.1 LTS (hardy)
My Ubuntu install was only about half a gig, so I had plenty of space for the carnal0wnage site even though the blog really takes all the traffic. I'm not going to do a lockdown guide, there are so many on the net, but you basically SSH in (also has a web console if you get locked out) and start "apt-getting" what you need to set up your box they way YOU want it. You also have full reboot privileges or if you really hose up your install you can just reformat.
Things I did:
installed stuff I probably don't need :-)
locked down sshd
installed apache2 and modsecurity
configured DNS for web and google mail
installed and configured denyhosts
started tweaking iptables rules
You can't beat 20 bucks a month for an IP and root on your own box ;-)
They also have an API so you can script management and status tasks