DOS games work great since DOSBox is inherently portable (you can grab DOSBox Portable from PortableApps.com but you might already have it).
You can also use a switch with ScummVM to store user data in it's folder instead of in AppData so you can take some SCUMM games.
Emulators are usually good choices as well for portability. For older systems the games are especially small. Only emulator other than ScummVM I see putting stuff in AppData is recent builds of VBA-M. DOSBox seems to too but I guess having a dosbox.conf in the dosbox.exe directory overrides that.
You can also put Portable Ubuntu on it (google it) but I couldn't get it to start up at a friend's house under Vista while it ran fine on my computer under XP. Annoying.
I have VPN software (OpenVPN) to connect to a VPN I use so I can remote desktop.
Hmm what else... you could put QEMU on there, it's the only really portable PC emulator/virtualizer (the virtualizer part requires a kernel driver but you can start/stop/install/remove it at runtime with some batch hax0ring). Then you can have an entire environment in there.
Another option is to use Ubuntu's USB disk creator tool and just make a bootable Ubuntu (I have one on a 1gb stick). Not too fun for already running systems, but you MIGHT be able to stuck QEMU on there too if you fit everything right and make it also run inside QEMU so it can run on an already-running system.
You could even in theory hax0r Portable Ubuntu to run similarly, but that probably wouldn't work right.
Oh don't forget my own
Google Chrome Portable (top two builds are the most recent).
Of course it mostly depends on where you use other computers and what you do with them (and what you can get away with doing on them).
[Edit: Oh yeah, backup. You can keep backups of important, non-replaceable files and still have plenty of room left for oldskool games.]