Most of the time when installing Linux on the Apple TV, you are doing it in order to unlock more capabilities when it comes to video playback and options; I assume this is what you are looking for. If you follow these recently updated instructions everything should go fine. Just be careful to read them thoroughly.
They will walk you through two different options: running from a USB stick and not touching the Apple TV hard drive, or installing Ubuntu (CrystalBuntu) on the Apple TV itself. I would highly recommend the first: In the case you don't like it, you can just power off, unplug the USB and, then restart; everything would be back to normal. It has both Mac and PC/Linux instructions in there depending on what you have to work with.
Install Instructions
I know that the link says things about XBMC but it is for installing Ubuntu on it so that you can run XBMC too, its a very good media player option. It involves installing Crystalbuntu, a port of Ubuntu with media player options using XBMC.
Here is a nice how to video as well that goes over the booting from a USB stick option:
http://www.youtube.com/watch?v=RJqyr0QRRvU
UPDATED
I understand that you want to do an install that will leave you with a desktop/server environment, which is also possible.
There are also a few other different options for installing a regular version of Linux, like Ubuntu 8.04 and even Arch Linux, with these, you will have a regular desktop and such, as you can see in this example video:
http://www.youtube.com/watch?v=ko0cwbGsKHU
This process, discussed here on Ask Different, goes over the way a bootloader can be copied and used to boot most versions of linux:
What Linux variants can be installed on an 1st generation Apple TV?
The direct page link is here:
http://code.google.com/p/atv-bootloader/wiki/InstallingLinux
This page, has talks about the atv (Apple Tv) Bootloaders and how to use them.
For simpler install though you can download and run there is the following link, which will install the OS of your choice on an USB Drive and do all the heavy lifting can be found here:
http://stmlabs.com/2011/03/28/crystalhd-released/
Here is a direct link to the installer download page with more instructions:
http://www.stmlabs.com/projects/crystalhd-for-appletv/
Also, if you google search "Install Linux on an Apple TV 1st Gen" you can find loads of helpful articles too.
I hope that this helps you out.
Best Answer
The 'All HD' menu (along with many others) apparently is loaded dynamically over the internet (presumably via a connection to the itunes store). If your Apple Tv is not connected to the internet this menu (along with others) will not show up.