In no particular order. These are things you might want to investigate for yourself. A listing here should not be taken as an endorsement. In fact, in many case I have not used the product and cannot comment on it.
Network-booting Your Operating System describes several techniques for booting across a network, using grub and some other tricks. I haven't tried it, but I have a sneaky suspicion that with an especially trained floppy diskette, you could get your entire first stage image onto the computer to be restored.
"Smart Boot Manager (SBM) is an OS independent and full-featured boot manager with an easy-to-use user interface. There are some screen shots available." It is essential if your BIOS will not allow you to boot to CD-ROM and you want to use a CD-ROM based Linux for Stage 1 recovery.
An old (2000) list of small Linux disties.
tomsrtbt , "The most Linux on 1 floppy disk." Tom also has links to other small disties.
The Linux Documentation Project . See particularly the "LILO, Linux Crash Rescue HOW-TO ."
The Free Software Foundation's QtParted for editing (enlarging, shrinking, moving) partitions.
QtParted looks to do the same thing with a GUI front end.
Partition Image for backing up partitions.
From the web page: "Partition Image is a Linux/UNIX utility which saves partitions in many formats (see below) to an image file. The image file can be compressed in the GZIP/BZIP2 formats to save disk space, and split into multiple files to be copied on removable floppies (ZIP for example), .... The partition can be saved across the network since version 0.6.0."
Bacula is a GLPled backup product which has bare metal recovery code inspired in part by this HOWTO.
"g4u ('ghost for unix') is a NetBSD-based bootfloppy/CD-ROM that allows easy cloning of PC harddisks to deploy a common setup on a number of PCs using FTP. The floppy/CD offers two functions. First is to upload the compressed image of a local harddisk to a FTP server. Other is to restore that image via FTP, uncompress it and write it back to disk; network configuration is fetched via DHCP. As the harddisk is processed as a image, any filesystem and operating system can be deployed using g4u."
"We present Frisbee , a system for saving, transferring, and installing entire disk images, whose goals are speed and scalability in a LAN environment. Among the techniques Frisbee uses are an appropriately-adapted method of filesystem-aware compression, a custom application-level reliable multicast protocol, and flexible application-level framing.