I researched this for several hours and came up with a few possibilities:
BasicLinux (4MB footprint) http://www.ibiblio.org/pub/linux/distributions/baslinux/
Haven't tried it but the footprint seems right.
Damn Small Linux (Business card linux distro) http://damnsmalllinux.org/
I don't think this is really designed for small memory needs, but the apps are good.
DeliLinux (486 linux distro) http://delilinux.berlios.de/
Made for a older machines. This looks promising but I haven't tried it. XFree 3.3.6 is supposed to be small and support older video cards. Slackware 7.1 based.
Aardvarks Dietlinux (distro based on dietlibc) http://lart.info/~bwachter/projects/dietlinux/
Dietlibc is supposed to be smaller and meant for embedded apps. Embedded distros have scared me off because they tend to have weird installation routines (build a filesystem on another linux box, generate an image, flash it to the device), although I'm very happy with Midori linux running on my MSN Companion. I use Midori almost daily and I'd love to make my AOLTV run it. Seems like a lot of work to build a new image, though.
Freevix wasn't a possiblility for AOLTV but it looked cool http://www.freevix.org/
Memory needs too high (sigh... wish we could upgrade). Freevix is a small bootable-cd-based Freevo Distro. It's like Knoppix if you want to try out Freevo (free-Tivo). Nice if you have a real computer with a vidcap card, but I digress.
Grey Cat linux (UMSDOS based, 8MB required, 386) http://home.wanadoo.nl/peterdekoning/30/index.htm
This is one of those funky linux distros that boot from a DOS filesystem with LOADLIN.EXE. I don't trust 'em, but haven't figured out why yet. The numbers are right. Worth a look.
KDrive http://www.pps.jussieu.fr/~jch/software/kdrive.html
Not a distro, but the newest version of the shrunken XFree86 server that works based on a framebuffer server. There was an old name for this project that escapes me at the moment. Search for Kdrive and Xfbdev. I wanted to incoroporate this into a Slackware-based AOLTV that I have running but I haven't got the time or knowledge. This is probably part of what you're looking for, unless you want to use SVGALib http://www.svgalib.org/
SlimLinux (DOS-based, busybox, uclibc, 8MB for current version) http://freshmeat.net/projects/slimlinux/
Another DOS-based distro. Fits on a floppy or installs to a DOS fs. Uclibc (or dietlibc) seems to a be another component to the small-footprint linux distros, as is busybox. Busybox lets you use a single binary for all of the major shell commands. Busybox is on Midori and I recommend it for small permanent storage requirements (not a problem on AOLTV) -- works great.
Tinylinux (386+, embedded slant, DOS based) http://tinylinux.sourceforge.net/
Haven't tried it but it's a quick 7mb download.
Vectorlinux http://www.vectorlinux.com/
Version 2 is known to work on AOLTV -- slowly. Contains a full version of XFree86. Maybe we can strip out X and use SVGAlib. I know there a version of Mplayer that uses SVGAlib.
Slackware http://www.slackware.com/
9.1 and 7.0 are only OSes I got to work on the AOLTV. I tried DOS/Win98/98lite (all had "Invalid system disk" error) and Redhat 8 and 9. Lilo's a little harder to configure but Lilo boot loader worked where Grub didn't. I'm currently using 9.1 because it recognized my USB network adapters better (DLink 650TX and Linksys). Use modprobe -k pegasus to find usb network adapters. I recompiled a slackware kernel on the AOLTV and it took 4 days. I'm planning to put SW9 on the 2nd partition of a 98lite installed drive and see if it can boot 98lite from there.
Hints: my google searches were for 486 linux and 8MB linux. There are tons of hits on embedded linux, and maybe that's what we want, but it sure seems harder than a pre-packaged distro.
