What's the best bootloader for an embedded Linux board?
Both the bootloader and Linux distribution depend on what your final application is.

RedBoot and uBoot are both popular bootloaders for embedded Linux. They support writing to flash, loading code over serial/ethernet etc. But, for a deeply embedded device, a very minimal loader might be better, leaving everything else to linux.

If you need access to a lot of software packages, you might try Debian's ARM port. For anything else, I'd recommend OpenEmbedded or Buildroot - both are configurable build systems for generating linux kernels and filesystems with only what you need and nothing else in.