I'm new to web administration but would like to learn so I am wondering what hosting service is the best option to be my playground. I'm not necessarily looking for specific names (although if there are some that would help) but rather what characteristics should I look for? Does it have to be dedicated or is SSH access sufficient (I want to install my own tools)? Is there some feature that would easily allow me to roll back something I messed up? Are there some that already have useful and user-friendly tools that some hosts offer (I use CPanel right now...)
If you're looking to do this purely for educational purposes you would be better off running it on one of your own machines. Many of us have development environments running as virtual machines.
e.g. I have a replica of the system which hosts our company web sites running on a virtual machine, which I start and stop as required. This allows me to experiment with no risk to the live site. For educational purposes, it would also help you to better understand the underlying systems, while giving you complete control of the environment. All this can of course be done at zero cost.
Take a look at linode.
You can put switch out linux distributions on your virtual server in a jiffy, create multiple hard disk images and switch out scenarios or projects.
Price is reasonable for what you get. There was a performance article about them that you can find digging around on the linode homepage.
Access is mostly through ssh. You have root and can configured, reconfigure, or mess up things to your heart's content. If you really mess up you can reset it to one of the default systems that they offer.
Amazon EC2 may also be worthwhile, and an experience people might look for on a resume. However, I found performance kinda slow when I tried it out and getting things up during the beta was kinda clunky.
If you truly want to learn about web administration you will stay away from CPanel and other web based administration tools. However, if you aren't familiar with web terminology or the core fundamentals then temporarily using CPanel or Plesk or the like may help you become comfortable with DNS, SSL, Virtual Hosts, etc.
You should look at installing linux in vmware server or parallels on your local workstation. Learn how to install and configure an http server, etc. Since it's only for the sake of learning there's really no need to pay just yet.
If you feel that you must have a server out on the tubes then check out VPS hosting from companies like Linode and Slicehost. They will allow you to reinstall or restore the OS from backups if you screw anything up (I use Linode & they're awesome).
Try to become familiar with the core of the OS before you get too deep into "web administration". Knowing the fundamental tools (cat,sed,awk,cut,xargs,find,vi,locate,which,man,STDIN,STDOUT,etc) will likely make any troubleshooting much easier.